O Evince usa as fontes padrão do sistema quando elas são especificadas no documento e as personalizadas quando elas são incorporadas. Isso sugere que o problema pode estar no seu conjunto de fontes. Se este for o caso, sugiro certificar-se de que o ttf-mscorefonts esteja instalado e atualizado.
Outra possibilidade é que o documento esteja usando fontes incorporadas que podem estar corrompidas ou que não foram baixadas corretamente. Você pode verificar as fontes selecionando "Propriedades" no menu e na guia "Fontes" (não consigo postar uma imagem porque não tenho reputação suficiente ...).
Outra discussão sobre essa questão referenciou outros leitores de PDF, sendo o mais popular o Okular (KDE), xpdf e epdfview. Você pode tentar um desses para ver se você prefere, mas eu não vi nenhuma solução clara para a questão de por que as fontes renderizariam melhor em qualquer um desses outros aplicativos do que no evince.