I came here hoping to find a solution to this same problem but alas the problem described is not even as severe as mine. I load my iPod Shuffle 1GB with the Autofill from a particular playlist. It shows 220 songs loaded (17.9 hours worth of music). I start the playback at work in the morning using random shuffle however it plays only like 3 hours worth before it starts repeating already played songs. I try everything to get to songs not yet played and it just keeps playing the same ones already played. I check the iPod in iTunes and it shows all 220 songs. There are no abnormalities with file names or anything and many of the songs have already played on other loadings. Also before going to the U2 concert I had cleared everything off my shuffle and loaded up only my How to Dismantle an Atomic Bomb album. Once again all songs show up in the directory but only two of them play. I switch off the random shuffle option but it still only plays the 2. At this point, I'm thinking I could have gotten better results just purchasing a 250 mb mp3 player. Please if anybody knows of a fix or solution I'm desparate for a fix.