I tried to play a DVD last night on my newly upgraded Ubuntu, it was horrible. I checked the usual stuff DMA was enabled it was, looked at the debugging info from Xine which didn’t really help.
Google is my friend in times of need, turns out I need to disable the X composite extension for frglx (the ATi binary driver) to work properly. An hour and several reboots later this simple fix fixed it, always they way. 
Ohh and I found this page useful, but I prefer to keep it simple. 