Open Synaptic. Install Totem-xine. While there install VLC. It is better anyway.

Your problem is related to the fact that Totem uses Gstreamer by default as its
engine and it does not work as well for playing DVDs. when you switch to Xine as
the engine it works better.

VLC has its own engine and it just seems to work for everybody.