Probably not correct mp4 formatting ... either the size or something else is not within the range. But normally you add them the same way you add songs. You can simply drag & drop them onto the iTunes Library icon at the very top of the playlists on left hand side of the program.

All mpeg 4 files I've come across have the .mpg extension. Which has made it difficult to know whether they were mpeg 1, 2 or 4.

Do you have QuickTime installed? I suspect on the Mac, iTunes uses 'some' of the QT codec libraries to help read/convert files. Not sure about windows.