once when i did a full restore, all my stuff sync'ed back to the ipod, except for my playlists.
then i saw that i hadn't checked the 'sync all playlists' box under the music tab on iTunes. have you taken a look to make sure you've told iTunes to sync all of your music? click the device link in the left sidebar to get to that.
(apologies if this is the first thing you tried -- no idea how long you've had your device.)