There is a package called mplayer-codecs that you may want to install. It tends to fix most of these slow video issues for me.

There is also a video player called vlc that also works pretty nicely. It's a little more configurable and flexible than mplayer and it can play a whole host of file types.

There is also meta-packages for codecs you can install. Namely gstreamer, gst-ffmpeg, gst-plugins-base, gst-plugins-good, gst-plugins-bad and gst-plugins-ugly - they install all the possible audio and video codecs you'll ever need. Yeah, Yeah, I know, it's a pain to install all those packages, but remember that with Windows you had codec packs. Think of the above as several codec packs thrown together.

@Trixar_za : Thanks for that. I tried vlc but it only gives video, not sound, with an error message ...

No suitable decoder module:
VLC does not support the audio or video format "mp4a". Unfortunately there is no way for you to fix this.

I installed the codec pack for mplayer but, having tried a few, the video is still slow and falls behind the audio. Doesn't happen if I watch the same vid on YouTube. Any other ideas?

Oh right, I remember now that stable's vlc's mp4 support is buggy.

A few ideas comes to mind. Right click the video window and go to preferences. Go to the Audio tab and make sure it's on ALSA, and enable the software mixer. You may want to normalize the audio if the sound is too soft. Next go to the Video tab and make sure it's using xv or x11. x11 doesn't always work, but for some reason it might magically start working after you install some other packages - don't ask me which or why, I just find it does that sometimes. Next enable direct rendering and frame dropping. Disable double buffering. Do not enable HARD frame dropping, just the one above it. Go to the Codecs and demuxer tab, enable Use non-interleaved AVI parser. Go to the Misc tab and Enable postprocessing and set it to 0 or 1. Now just click ok and restart Mplayer. It should run the mp4 movie a little better now.