I am having the same problem. I partially solved it as such:
Quoting the xinehq website FAQ:
This points to a problem with the Xv extension, which is used by xine to display the video image. To verify this, try running xine with the XShm video output plugin:
xine -V XShm
If that works fine, you just proved, that the Xv extension is buggy. xine will remember the last used video output plugin, so the setting will stay at XShm. You could simply continue using this, but XShm is a lot slower than Xv, so read on and see if you can get it working. Usually you should look for updated versions of the XFree driver module that belongs to your graphics card.
------ end of quoted material
Running xine that way (without the Xv extension) worked pretty well. Run xine-check at the command prompt to check out the xine status. Even though it seem to recognize the Xv there it doesn't work. May have simething to do with the fact that FC2 is not Xfree86 but is the newer X11/X.org video system.
Maybe some more configuration will solve this one.
I still have not figured out how to get Totem to work. I HAD the same error you quoted then I upgraded versions and Totemwon't even start and the messages changed to something about 2 threads (I'll post it later when I get a chance to look it up again).