Although a video may say it's an "MP4" file, that does not actually mean it is the same format as another "MP4" file. In basic terms, (from what I can understand - I'm not an expert!) MP4 is a general term which can include different formats, not all playable by the iPod.
Forum contributor Jeff Bryan has mentioned the requirements for a video to play on the iPod in another post (here:
http://discussions.apple.com/thread.jspa?messageID=8341329� ), but as he has quoted an Apple spec, I'll re-quote it here (hope you don't mind Jeff).
There are the specs Apple quote.
The file must meet the following specifications to play correctly.
H.264 video: up to 768 Kbps, 320 x 240, 30 frames per sec., Baseline Profile up to Level 1.3 with AAC-LC up to 160 Kbps, 48 Khz, stereo audio in .m4v, .mp4 and .mov file formats
-or-
MPEG-4 video: up to 2.5 mbps, 480 x 480, 30 frames per sec., Simple Profile with AAC-LC up to 160 Kbps, 48 Khz, stereo audio in .m4v, .mp4 and .mov file formats.
You'll notice that MP4 appears twice - two different specifications! Those are simply the ones that play on the iPod though! So presumably, the videos you have which will not play do not meet these specifications. If you read the complete post/thread, you may find more information that will help you, including methods of converting videos so they play on the iPod.
Good luck.