I too would check the battery, but also the starter and wiring. You see, I have the odd habit of replacing the main positive (battery to starter to alternator) and negative (battery to, well, you know. Also the big transmission to ground) wires with 4Ga welding cable and copper ends. But, I have seen the starter solenoid wire (the one from the ignition key) go bad in other cars *and* the solenoid itself take a dump.