Sai, i calcolatori sono relativamente stupidi; essenzialmente perché non sono intuitivi.
Se il logo del tuo primo messaggio dice che stavi usando TeXLive/Debian, vuol dire che stavi usando TeXLive/Debian. Qusta è la loro stupidità; se anche kpsewhich ti risponde da terminale che il file pdfttex slo torva con il path che comincia con /opt, è corretto, ma stai chiedendo una cosa al terminale, non a KILE oa ad altro programma di Ubuntu che lancia la compilazione di TeXLive/Debian in background.
Se lavori con TeXstudio o con TeXworks, configurati correttamante per usare la verisone TeXLive/CTAN, il problema non ti succede.
Se puoi configurare Kile o altro programma Ubuntiano per usare al TeXLive/CTAN il problema sparisce.
Ed è il solito problema delle macchine conformi a Debian che non sono completi e spesso sono fortemente in ritardo rispetto agli aggiornamenti che invece avvengono su CTAN quasi ogni giorno.