Gostei muito do tópico, vi que não é um problema novo e eu mesmo "sofro" dele. Já começou bem, Eureca seja bem-vindo!
Como sou muito preguiçoso e raramente uso aquele "Abrir com outro aplicativo" não tinha procurado uma solução até agora.
Pois bem, fiz uma pesquisa. Olha o que eu encontrei:
http://ubuntuforums.org/showthread.php?t=1273296http://ubuntuforums.org/showthread.php?t=1359664https://bugs.launchpad.net/hundredpapercuts/+bug/488547https://bugzilla.gnome.org/show_bug.cgi?id=586040Está tudo em inglês mas até onde eu chequei as informações conferem, ai vem a noticia ruim, aparentemente não exite uma solução definitiva.
Você deve ter itens duplicados em ~/.local/share/applications --isso deve servir no caso do wine--. Mas antes de excluir dá uma olhada nas propriedades do ícones na parte de comando, deve ser alto explicativo.
No caso do brasero, do Visualizador de área de trabalho remota e F-spot é mais um caso de "nome ruim" olha em /usr/share/applications eles estão lá aos pares mas se você olhar nas propriedades os comandos são diferentes. Não recomendo a exclusão.
Não testei aqui, não uso o wine por isso não incomoda. Para testes, no lugar de remover definitivamente o ícone, só muda ele de pasta e usa por um tempo, ser funcionar dá um retorno.