The problem is that while your iPod uses the .mp4 file container for video, there are codec discrepancies that prevent them from working on it.
If you're using Mac, try iSquint, it's free. iMovie, Final Cut Pro, and Quicktime Pro are better, but they cost money or piracy skills.
EDIT: Try out Handbrake or ffmpegX