Isso funcionou para mim no Debian Jessie:
sudo aptitude remove fonts-texgyre
O comportamento vem das fontes TexGyre sendo substituídas por Times e Helvetica quando aparecem no pdf. Eu acabei instalando-o como um dos pacotes recomendados do TexLive, então, esperançosamente, removê-lo não quebrará nada.
Esta resposta foi parafraseada de este relatório de bug do Ubuntu e confirmou neste.