Odd problem.
Have you double-checked to make sure that those specific playlists that are set to automatically sync to your iPod are properly checked in your iTunes preferences?
If so, I would say it's an iPod issue & your best bet would be to restore the iPod to factory defaults. Do this by first connecting your iPod to your computer, then find the 'iPod updater' software on your hard-drive (the latest version was released 11/17 - and should have that date next to it). Click on it, and hit 'Restore'. A message saying "Are you sure you want to restore? All data on your iPod will be erased." [or something similar] will pop-up... and obviously, you still click 'Restore'. This will delete all your files on your iPod but hopefully it will help solve your problem.
Good luck.