Simples de resolver sem linha de comando ou sudo . Basta excluir o diretório ~/.wine que está na sua pasta pessoal (onde ~ é a abreviação de /home/username ). Você terá que mostrar arquivos ocultos para encontrá-lo. O Wine irá reconstruir automaticamente este diretório na próxima vez que você usá-lo.
Embora essa seja a maneira rápida e fácil, ela deixa as entradas restantes em ~/.local/share/applications . Basta navegar até esta pasta e excluir os arquivos / diretórios indesejados deixados dos aplicativos instalados do Wine. Se você não fizer isso, os aplicativos removidos ainda serão listados nos menus da área de trabalho, mesmo que eles não estejam mais instalados.
Eu uso playonlinux para ajudar com o Wine. Isso torna mais fácil e permite que cada programa que você instala esteja em sua própria pequena unidade virtual separada do Windows. Então, se você tiver esse problema novamente, basta excluir o diretório de programas, em vez de todas as suas informações sobre o Wine.