Il problema delle versioni Debian è che il processo di “debianizzazione” è lungo, quindi le distribuzioni debianizzate di qualunque cosa, TeX Live compreso, sono sempre relativamente obsolete.
Installa a fianco della tua distribuzione debianizzata di TeX Live (che serve per soddisfare le dipendenze Debian) la versione TeX Live 2011 come ti ha suggerito Enrico; io lo faccio sempre sulla mia Ubuntu virtuale e funziona benissimo.
La conversione automatica è che quando cono un sorgente da compilare con pdflatex inserisci una figura EPS con \includegraphics, lui, pdflatex, se la converte da solo in formato pdf e se la include come farebbe con le altre figure nei formati pdf, png, jpg. Manco te ne accorgi che pdflatex ha consumato alcuni millisecondi per convertire l’immagine in formato pdf; per altro è una cosa che fa solo una tantum, non è che ripeta inutilmente una conversione che ha già fatto.
Installando TeX Live 2011, esegui l’installazione completa, non stare a lesinare sullo spazio disco che consumi, a meno che tu non sia proprio alle strette (ti occorrono un po’ meno di 3 GiB di spazio su disco); a parte la possibilità di poter aggiornare la TeX Live 2011 con la frequenza che ti pare (per esempio ogni 10 giorni — impossibile da fare con la versione debianizzata) non ti pentirai mai di avere tutto quanto a tua disposizione, senza doverti preoccupare di installare nuovi pacchetti ogni tanto; ci pensa il TeX Live Manager a farlo per te ogni volta che esegui un aggiornamento generale.