Eu estava tendo o mesmo problema no Ubuntu. A execução dos seguintes comandos no terminal funcionou para mim:
$ cd /usr/share/applications
$ xdg-mime default evince.desktop application/pdf
De acordo com esta resposta , você pode verificar $HOME/.local/share/applications
também, mas isso não foi necessário para mim.