First get them codecs from :
http://packman.links2linux.org/ (libdvdnav, libdvdread, win32 ...ect.)
Second remove ALL traces of "Xine" from the hard drive. Totem is just a front end to Xine. Don't forget .xine folder from your home.
Third download libdvdcss source.
http://download.videolan.org/pub/libdvdcss/1.2.8/
Compile it.
Fourth download xine-lib from :
http://xinehq.de/index.php/releases
Compile it. You may have to remove and then compile totem(not sure).
How to compile:
Extract the tarball
open terminal
cd into directory where you have the uncompressed folder cd /home/you/xine-lib
type ./configure
type make
type su then your root password
type make install
type /sbin/ldconfig to update library links
Keep your fingers crossed and hope for no errors