A solução é simples.

Começou a acontecer aqui comigo no Linux Mint 13 com MATE.

No MATE, os programas têm nomes diferentes daqueles do GNOME, então, o sistema deve ficar meio indeciso com o que fazer e "last resort" para o Firefox...

O leitor PDF padrão do GNOME é o Evince. O mesmo do MATE é chamado Atril (WTF???).

Para corrigir, execute no terminal:

xdg-mime default atril.desktop application/pdf

Troque "atril" pelo seu programa preferido

Exemplo: Evince, Adobe Reader, Sumatra, Foxit...

Abraço!