From what you have described, it sounds like the battery isn't providing enough power to the starter.
You might want to check the date code on your battery. If it's around 3 years old or more, you probably need a new battery.