I wasn't able to find the solution.
For anyone else's benefit, what I did was went to the Apple store and spoke to a technician, who didn't know, who raised it with another technician, who didn't know, who escalated it to a senior technician, who had never seen this problem. (They verified that the problem existed.)
I wiped the iPod completely by using iTunes Restore, and now it works fine.
He did suggest not to manually drag files to the iPod, but rather create a playlist on the desktop machine, and let iTunes auto sync that.