βρες που είναι εγκατεστημένο το binary του xelatex. Δοκίμασε να το τρέξεις από την τοποθεσία που βρίσκεται (πχ /home/username/texlive/.../xelatex) Θα πρέπει να τρέχει κανονικά. Αν όντως τρέξει δημιούργησε ένα symlink στο φάκελο /usr/bin. Μετά από αυτό θα βρίσκει το xelatex.
Πάντως δεν είναι λογικό ότι δε σου βρίσκει το xelatex και βρίσκει όλα τα άλλα... Αν υπάρχουν άλλα πρόβληματα όμως, όπως με το xgreek που έλεγες αυτό δε θα στα λύσει.
Σαν ύστατη λύση θα μπορούσες να δοκιμάσεις να ξαναεγκαταστήσεις όλο το TeXLive σαν root. Το ξέρω ότι δε συνίσταται αλλά πιθανά να παίξει.
@eumetaxas ή άλλοι με ubuntu
κανένα ppa με πιο καινούρια πακέτα για LaTeX δεν υπάρχει?


