Movies need to be in either mpeg 4 or H.264 format which is an advanced mpeg 4 format. You can add files manually to your iPod. Perhaps you can try that for the movies for your iPod. Manual Updating of iPod;
How to transfer to my iPod (& iTunes) - for video