try to reset to factory settings.
When i got my 80gig ipod classic, i tried to make it sync any videos in itunes, but not sync the music. For some reason that screwd up and it either sync'd both of em, or nothing would go on. I reset to factory settings and did everything manually and it worked.
Main thing is, try to reset to factory settings, there should be some option in the ipod or, when connected to pc, itunes.
If not, post a screenshot of the error msg.
EDIT: actually i think i got that same message. Try disabling the sync and manually put the videos. I had my problem when i first got my ipod, so it was empty then. If your's is empty (somehow i doubt) then reset to factory settings, if not, then try unsyncing and manually transferring, if doesnt work then u probably gotta reset.