I am having problems playing a few MP4 video files with MPlayer on my N800 also. The video and audio stutter during playback. This has happened on R14 and R15 of MPlayer. I have not tried R13. These files play fine in the built in Media Player and in Canola.
I originally converted these files from .mov files.
Here are the video file details of one of the problem videos...

Source: C: \Documents and Settings\HP_Administrator\My Documents\My Videos\Nug and Sally.mp4
Format: Apple MPEG 4 Decompressor, 176 x 144, Millions
AAC. Stereo (L R) 44.100 kHz
Movie FPS: 15.00
Playing FPS: (Available when playing)
Data Size: 1.95 MB
Data Rate: 43.48 KB
Current Time: 00:00:00.00
Duration: 00:00:45.28
Normal Size: 176 x 144 pixels
Current Size: 176 x 144 pixels