I had the problem where my purchased songs would be skipped over when I attempted to play them on my iPod, described perfectly in article 303854 "iPod does not play content purchased from the iTunes Store." However, after following all the steps in that article the problem still happened, until...
I spoke with an iPod support representative who knew that in some cases the normal iPod Restore steps don't work unless the iPod is put in "Disk Mode" first. We put my iPod in Disk Mode then performed the Restore steps, and the problem went away--purchased songs played normally.
For instructions to put an iPod in disk mode, see article 93651 "Putting iPod into Disk Mode":
http://docs.info.apple.com/article.html?artnum=93651
So, if your purchased songs are skipped over and if the steps in article 303854 don't solve your problem, consider putting your iPod in Disk Mode first then performing the Restore steps again.
Good luck.