I've tried totem and vlc. Both have the issue, especially when running
in full screen.
The system is a core i7 920 with 12GB RAM and ATI 5850 (fglrx) running
ubuntu 9.10 64-bit.
I don't have this problem under ubuntu 9.04 with a core2 quad and nvidia
fx370. In fact, I have 9.04 and compiz running on a first generation
asus eee and I can run full screen video with both totem and vlc.
[and, fwiw, I'm running 9.04 under virtualbox on a mac, and compiz is a
little choppy, but vlc plays fullscreen fine]. My hunch is that it may
be related to the 9.10 upgrade... do you have another machine that you
could try out 9.04?
You may want to check the ubuntuforums and see if others are
experiencing this type of problem under 9.10. I always hold back on the
distribution upgrades for a few months until most of the kinks get
worked out. There's no reason you should be seeing video problems with
the hardware you have...