Try this: Go to Applications menu. Click on add/remove, sound and video, tick both Gstreamer extra plugins and Gstreamer ffmpeg. Install and video should work ok. I just tried it for myself.
Just noticed I've also got Mplayer plugin for Mozilla installed from add/remove too...this may be the one you need...
Ah, and I've got Xine extra plugins too. That just about covers it.
Celeron 2.8 Ghz 512 MB RAM 2* 80 gb HDD dual-boot Linux Mint / Xubuntu 6.10
AMD Duron 800Mhz 256 MB RAM 20 gb HDD Xubuntu 6.10