This is a known feature absence. Enough people have been annoyed by it that I’m sure a bug report/feature request has already been filed. No idea if it will ever be reimplemented though. Supposedly, artwork is already part of the music file, and all the art syncing option did was get rid of the extra thumbnails, so theoretically it didn’t save all that much space anyway.
Not sure why you’re having this problem. If I go to the ipod syncing in itunes, and click on the movies tab, I see three headlines:
include movies from playlists:
The last one will let you sync video playlists. Maybe you just didn’t scroll down to see it?
If you still can’t find it, if you select your video playlists in the music section instead, they should still show up in the video playlists on your ipod.