Thanks Dr. Tyrell, that fixed xine / gxine for me! Using XvMC gives a very nice improvement in CPU usage over plain Xv.
Unfortunately MPlayer is still crashing with XvMC. Turning off composite didn't help and neither did switching the -vo -vc order. But I'm starting to think it's probably a bug in the Ubuntu MPlayer package since Xine has no problems with the XvMC extension. Time to file a bug report.