iPod Shuffle "forgets" iTunes songs

I have searched various iPod sites with no luck. Can anyone provide an explanation, or even better, a solution?

My iPod Shuffle periodically loses my iTunes songs. It keeps the songs that I have added from CDs. When I sync the Shuffle with my computer, I can get the iTunes songs back. Still, this is very annoying since I can go to exercise and wind up with only a few songs on the shuffle.

I’d recommend doing a restore on the iPod. It sounds like the music database is getting corrupted (pretty much the main reason why songs “disappear” from the iPod… they’re there, the iPod just can’t see them in the database). Then, copy the music back from iTunes. If that doesn’t fix it, you’ve likely got a problem with the iPod itself.