i had this same problem... here's what caused it to happen:
on an average day, i connect my ipod to three or four computers, three macs and a pc...
i've purchased songs on all of these machines.
here's the catch: if i purchased a song on one of the macs, and the pc is the last machine i've sync'd the ipod to, then it will skip those songs, only playing songs i've loaded on with the last sync'd machine (or music i've loaded via cd)
make sense?