Ok, BIG error. I just realized that I hadn't installed libdvdcss, just installed and now everything works fine. Sorry about the hastle everyone. For those having similar problems try starting xine from command line and start playing a dvd, if you see that there's no dvd encryption support (check the command line) install libdvdcss.
I was tricked because I had a French dvd that wasn't encrpyted, so I thought everything was installed. Hoorey for the French for not encrypting their dvds (Le Gendarme de St. Tropez

)
Sorry about the hastle again.