[mark houghton]

Before you throw the baby out with the bath, do check that your battery connections are also clean....as well as the ground strap that connects from the body to the transmission. That's "usually" the culprit in any car, where you have good enough connections to activate the starter solenoid (low amp draw) but not good enough to turn the starter motor which pulls a lot of amps.
If it ends up being the starter, I can't recommend which option to go with.