I had the same problem. I run Ubuntu 9.10 but I doubt this issue has much to do with the version of ubuntu. If you have all the dvdcss stuff installed AND VLC doesnt work (has css built into it) then it is not likely css.
I looked into the /var/log/syslog file and found an error about the region not matching.
So I ran regionset (see this link for more information: https://help.ubuntu.com/community/RestrictedFormats/PlayingDVDs) and set the region from FF to FE. FF i think is "not set" and FE is region 1.
sudo apt-get install regionset
regionset version 0.1 -- reads/sets region code on DVD drives
Current Region Code settings:
RPC Phase: II
vendor resets available: 4
user controlled changes resets available: 5
drive plays discs from region(s):, mask=0xFF
Would you like to change the region setting of your drive? [y/n]:y
Enter the new region number for your drive [1..8]:1
New mask: 0xFFFFFFFE, correct? [y/n]:y
Region code set successfully!
Then dvd playback worked perfectly.