Hmm... It sounds deeper than the problem I described. Wait - I bet you have a bad/corroded connection at your battery. The battery terminals are possibly dirty.(either between the battery post and terminals, or between your battery cables and your terminals) This would be the first area to check.
