Did you clean where the battery cables connect to the terminal(under the bolts/metal plate), and where the terminals connect to the battery? Your problem sounds like a poor connection somewhere... It always used to happen to me.(especially on a high humidity day) Your ground strap might need to be cleaned where it connects to the frame - also both sides of the ground strap from the frame to the engine. Make sure all your connections are tight, too.
