Isso soa como seu banco de dados de pacotes está estragado. Primeiro eu identificaria todas as versões de xdg-open que você tem em seu sistema. O type sempre deve ser usado para executar essa tarefa, never confie em which ou whereis .
Exemplo
Identifique todos os xdg-open .
$ type -a xdg-open
xdg-open is /usr/bin/xdg-open
Descubra de quais pacotes eles são parte.
$ dpkg -S /usr/bin/xdg-open
xdg-utils: /usr/bin/xdg-open
Você desejará repetir o dpkg -S .. acima para cada correspondência retornada por type -a ou usar essa dpkg -S .. search.
$ dpkg -S xdg-open
xdg-utils: /usr/bin/xdg-open
xdg-utils: /usr/share/man/man1/xdg-open.1.gz
Eu faria cada um, um de cada vez.
Reinstalando o xdg-utils
Se você quiser atualizar a instalação deste pacote, faça o seguinte:
$ sudo apt-get --reinstall xdg-utils