Para mim, o wine foi instalado como vários pacotes com versões diferentes - por exemplo, wine1.4
ou wine1.4-i386
.
Para remover todos eles, eu simplesmente digitei sudo apt-get purge wine
e pressione TAB para exibir todos os pacotes instalados com o nome começando com 'wine' e removendo todos eles. É claro que sudo apt-get autoremove
foi necessário no final para limpar pacakges desnecessários.
Nota: Tenha cuidado com sudo apt-get purge wine*
, pode remover mais do que você realmente quer! - veja esta questão para mais informações.