First of all, try putting it on charge and leaving it there for about 8 hours, and see if that helps at all. If you're charging it for only say 4 hours it'll be 70% charged or so, but show as being almost 100% charged. (It trickle charges for the remaining time.)
Rechargable batteries do stop working properly after so many cycles, however. The iPod uses a rechargable batteries, so is susceptable to this. Apple has come under fire since the iPod was released over this, since they don't make it easy to change the battery like you can for your mobile phone.
You can get replacement battery kits from many places, such as
here. If you're confident that you or a friend can change the battery yourself (read the instructions first to see, on the website), then do that. If not, places like the one I linked to offer a service where they'll change the battery for you. Apple also provide a similar service, but charge too much for it I think.