Totem just says:
"The source seems encrypted, and can't be read. Are you trying to play an encrypted DVD without libdvdcss?"
I HAVE got libdvdcss installed confused!?
EDIT: EH? Ejected the DVD and inserted it again, and it works... Oh well ..
EDIT: Ok the video is all inverted colour-wise now, like it's not playing it in the right format (it should be playing it as PAL)
EDIT: Restart Xorg, and now everything works. This is all very weird...