(Para a solução, pule para o final. Vou explicar alguns detalhes técnicos caso seja útil para alguém tentar entender por que isso acontece.)
O problema é que existem vários arquivos .desktop para esse programa com diferentes nomes de arquivos em applications diretórios.
No Ubuntu, os diretórios applications são:
~/.local/share/applications
/usr/share/applications
Por exemplo, no meu sistema, há três entradas para o Banshee em /usr/share/applications/ :
/usr/share/applications/banshee.desktop
/usr/share/applications/banshee-audiocd.desktop
/usr/share/applications/banshee-media-player.desktop
que resulta em três entradas para o Banshee no diálogo Open With Other Application... .
Uma solução é excluir os arquivos .desktop extras, mas isso pode impedir a abertura de outros tipos de arquivo (por exemplo, banshee-audiocd.desktop é usado para abrir CDs de áudio).
A solução certa é adicionar uma linha Hidden=true a esses arquivos .desktop duplicados em /usr/share/applications/ . No entanto, eu não recomendo que você faça isso porque requer mexer com arquivos de sistema de propriedade do root (essa correção deve estar lá por padrão).
Então, o que você pode fazer até que isso seja corrigido no Ubuntu?
Solução
Lembre-se de que eu disse com nomes de arquivo diferentes no começo? Isso porque .desktop arquivos em ~/.local têm maior prioridade sobre os arquivos .desktop em todo o sistema com o mesmo nome. Portanto, copie as entradas das quais deseja se livrar de /usr/share/applications para ~/.local/share/applications e adicione Hidden=true a elas.
Problema resolvido!