Urm, I'm on a Mac if that's an issue. Have tried MPlayer X, Quicktime and VLC.
I haven't messed with a Mac in a while.
But you mite want to download a newer codec pack for the Mac from one of the shareware sites such as...
http://mac.softpedia.com/http://download.cnet.com/mac/etc...
VLC is one of the best video players around for the PC. But the Linux version is not as good. Macs are now running an Apple version of Linux so VLC mite not be your best choice of players.
I've ran into a few quirks with certain video clips on windows, if you rename the file to one of the other mp4 video extensions like .M4V, or .DAT it mite play better(What I believe happens is with a different extension it defaults to a different codec and that's why the files play better.). I'm not sure if this will work on a Mac, but its worth looking into.
Also if you have a DVD player app installed, most of them will play a mp4 file.
Another possibility is some other app is hogging resources on your Mac, you should try unloading unneeded apps when you play videos.
You mite also want to ask for help on the Mac forums.
http://forums.cnet.com/mac-forums/http://www.mac-forums.com/forums/etc....
I did a little look-see and "Niceplayer" is recommended, but since I don't have a Mac I can't tell you if it works well or not. (The download link is on the side panel.)
http://code.google.com/p/niceplayer/