Scommento che sul tuo Linux/Mint ha una TeXLive/Debian; lo puoi sapre per certo leggendo el torme righe del tuo file .log.
Può essere che tu abbia una versione TeXLive/CTAN, ma se usi Kile, è possibile che lui udi la versione Debian.
Prova a installare TeXstudio (multipiattaofrma); lui se è instlalata la TeXLive/CTANcompleta e aggiornata, non avrebbe problemi a trasofrmare attraverso pdfLaTeX+epstopdf (che non hai nessuna bisogno di esplicitare fra i pacchetti da richiamare con la TL/CTAN) tutte le tue immagini eps al volo.
Poi in futuro cerca di liberarti della dipendenza dal formato eps; le poche volte che ti potrebbe essere necessario, puoi sempre usare pdf2ps (o simili applicativi); Io non ricordo da quanti anni, forse 10, non uso più immagini eps. Anzi, no, uso tiger.eps distribuito insieme s ghostscript per fare qualche esperimento di conversione, ma non per produrre documenti. Sono ingombranti perché son in testo puro e non contengono più informazione di quella contenuta nei corrispondenti file pdf, che invece sono compressi.