Puoi trovare i codec sul sito di mplayer http://www1.mplayerhq.hu/MPlayer/releases/codecs/. Li installi in una cartella (io ad esempio li ho messi in /usr/lib/codecs ) e poi nelle opzioni di Xine inserisci questo path.

Edit: dimenticavo: