DVD Playback on Ubuntu Gutsy

This afternoon, while doing nothing in particular, I decided to listen to one of my Jools Holland DVDs. I popped the DVD into my laptop and started Totem, only for Totem to spit out an error message. The error message told me that I didn't have the correct plugin to handle DVD playback and pointed me in the direction of this page: http://www.gnome.org/projects/totem/#codecs

I checked my system to make sure I had the listed plugins and found that I already had them. I then realised that I hadn't actually tried to playback a DVD since upgrading Ubuntu from Feisty to Gutsy.