Are the videos still in iTunes when you try and update the iPod? If not and if you are using Automatic Update then files that are on the iPod that are not in iTunes are removed to prevent Piracy. You can actually use the Manual Update to update your iPod.
/ 
