Ive done about everything I can think of. I have followed the RestrictedFormats wiki page and the Medibuntu pages. I am running Ubuntu 8.04 in Gnome on a 64bit Intel Pentium D with 4GB of RAM.

All video formats I have viewed(wmv,mov,mp4,avi,flv,mpg) are extremely choppy, and become more choppy the closer they get to full screen. My audio works fine for all of the above listed formats. I have the following video players installed, in some of the some video plays, in others they dont. Either way, its either a black screen with audio, or its really choppy with audio.

GNome Mplayer
Mplayer Movie Player
Movie Player
VLC Media Player

Any help or pointers would be greatly appreciated. If you need anymore info on my setup, Id be happy to provide.