My iPod did the same thing a while back. Funnily enough, it happened immediately after I had charged my Ipod using another person's charger at their computer.

What you did (deleting and re-uploading) is probably fine. Since it happened to so many of my songs, I panicked and deleted my entire iTunes, reset my iPod to its factory settings, and re-uploaded all my songs. In retrospect, it was probably overkill. :)