There are couple of similar topics here and here, but the gist of the answers is to do what's stated in the documentation.
These are the commands I've already run
sudo apt-get install ubuntu-restricted-extras
sudo apt-get install libdvdread4
sudo /usr/share/doc/libdvdread4/install-css.sh
sudo apt-get install libdvdcss2
sudo apt-get install w64codecs
sudo apt-get install gstreamer0.10-plugins-bad
sudo apt-get install gstreamer0.10-plugins-ugly
and probably some other codecs and whatnot that I can't remember at the moment.
I've tried three different DVDs on both VLC and MoviePlayer. VLC gives the error "VLC cannot set the DVD's title. It possible cannot decrypt the entire disc" and then plays the FBI warning before exiting with more errors like that. MoviePlayer just plays the warning and exits without error (kind of annoying).
I'm running Ubuntu 64-bit desktop 11.04. What else can I try to fix this? I'm having trouble troubleshooting this issue because it seems that every website just says to do the above.