On my ubuntu box I have had an interesting issue;

when I play some dvds they work fine but others wont be read by my media players (totem and vlc).
I noticed that the ones that played were the region 0 DVDs (often cheap bargain bin type dvds from tescos ) but the dvd's that wouldnt play were the ones that were specifically European/UK dvds (regions 2 and 4).

I have most if not all of the multimedia codecs installed, but this might be a hardware issue...I'm not sure (although my region 2 & 4 dvds played fine under vector linux).