Every Ubuntu release before 2008, i has the custom habbit of switching totem with its gstreamer backend to the version with the xine backend. Xine is a really good player, which i have used intensivly before switching to Ubuntu. Why did i change to the xine variant, simply because the gstreamer backend wasn't able to play everything, it got better each release, but each time there were still some files that didn't play well (or at all). About at 2008 gstreamer got to the point it did play everything i threw at it, so there was no reason to switch anymore, i think nobody does these days.
After upgrading to the latest 9.04, everything worked as expected, no problems on my home-pc. At work i don't play a lot of movies and it wasn't until we got a videocast of one of our c*o's that i noticed video didn't work anymore. Everything worked just fine at home, so there had to be something else causing the issue. One of the major differences between my home and work-pc was the video card, at work it uses the radeon driver. I solved it by starting up 'gstreamer-properties' from the command line, which allows you to configure some minimal aspects of the audio and video output/input of the gstreamer framework. In the video tab there is the option to adjust the output mechanism, after selecting 'X Window System (No Xv)' everything worked perfectly. The disadvantage of this approach is that no acceleration is done, this means playing a video takes seriously more cpu, which could give problems on older system (but it's still better then no video i suppose).