In my case the songs would sync to the iPod, just not in the particular playlist. I had a look through the Apple support forums as well and someone there suggested (unsurprisingly) resetting the iPod.
I'll try the check/uncheck trick this evening and see what happens.
Many thanks for doing the experiment!