Apenas um tiro --- você tentou instalar gsfonts-other
?
apt-get install gsfonts-other
Por outro lado, muitas vezes tive esse aviso sem efeitos nocivos na minha saída - verifique se é esse o caso. Aconteceu quando os dvips engoliram alguma figura ".eps".
(Caso contrário, tente adicionar um pequeno arquivo de exemplo - para que as pessoas possam verificar).