That happened all the time with my 20GB one. I'd pick a song, slide it back into the case, put it on the tray on the dashboard, and the song AFTER the one I'd picked would start. Happened 1 out of 3 times, at least. VERY annoying. If I waiting until the song started to play (and just stared at the screen) to slide the case around it, then it was fine. Grrr. Frustrating to hear that problem hasn't gone away...
My new 30GBer is on song 2445 of 5649 as we speak. I re-ripped most of my music in AAC 128bps after having it in 160bps MP3. I went from 4761 songs on 23.68GB to 5649 songs on 23.72 GB. That's including the addition of a Michael Crighton audiobook (200 MB altogether)!
Anyway... back to topic. Um, yea! Annoying!!