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.