iPod won't hold a charge even AFTER replacing battery

After 2 years, my iPod stopped holding a charge. I would plug it in and after a couple seconds i would get the red battery icon saying the battery was low,but with the plug over it indicating that charging was complete. Sometimes it would show it was charging and the indicator would go green, so I would leave it. But when I came back to it the battery had drained instead. I just replaced the battery on it figuring that it was the culprit and was ecstatic when it charged right up, but after I synched it it was back to it's old shenanigans. Any ideas?