From the xine website:
Please Note: the dvdnav plugin has been merged into the xine-lib tree, so for normal users it is no longer necessary to install any external DVD plugins. However, for encrypted DVD playback libdvdcss is needed.
So you'll probably need libdvdcss. Then get the newest version of Xine and install.
Boring sidenote: Xine was the first ever program I compiled in Linux. Before that, I'd been using rpms.