Enable the iPod for disk use. See
How to enable disk use.
Go to "my computer" and from the tools menu/folder options/view tab, enable "show hidden files and folders" in the advanced settings pane. Open the iPod in "my computer". Look for a file called "iEKinfo". Is it there? If so, make a copy of this file and save it somewhere easy to find (the desktop for instance). Do this also with the "iTunes DB" file. Don't worry if you can't see these files.
Create a new administrator account. Log out of the current account and log in to the new one. Then
restore the iPod to factory settings.
Open iTunes, connect the iPod and set the transfer preferences to
manual transfer. Then download the free single of the week from the iTunes Music Store. Verify that song plays in iTunes.
Now, drag
this song only to the iPod, and eject the iPod from iTunes and disconnect it from the computer.
Does the song play on the iPod ok? If so, log out of the new user account and log back in to your normal one (the one you have issues with) and reconnect the iPod to the computer. Keep manual transfer selected for the moment. Drag some of the older purchased music (the ones that wouldn't play before) to the iPod.
Eject the iPod and disconnect it. Do those songs now play ok?
If not, first try this step.
Delete the SC Info.sidb file. Open iTunes again.
Now transfer some of the affected music to the iPod again. Does it play ok?