Are these just plain old playlists and not Smart Playlists (i.e. have a gear icon on them in the left hand pane in iTunes)?
It could be that the songs you have added to the playlist are configured not to sync to the iPod still. What options and configurations do you have in place from under the iPod's Summary and Music tabs in iTunes?
It's a plain old playlist (with a folder icon next to it). One more fact to complicate things. I just had my hard drive replace under a recall from Apple. Before I replaced it, plain old playlists worked fine.
But I may have just solved the problem. When I was having the problem, I was creating the playlists by going into the "File" tab and clicking "New Playlist Folder". This time I clicked the + sing in the lower left hand corner of the iTunes window. Instead of a file folder icon, there's now a musical note. And the songs now seem to be staying. I'll also play with the smart playlists and see if that help too. Thanks B-Rock for inspiring me to explore a bit more.