Você pode querer fazer um backup seguido por uma reinstalação completa.
Acabei de testar isso em uma máquina virtual para ver os efeitos.
sudo apt-get remove wine\*
Isso me avisou que eu estava prestes a remover 120 pacotes, incluindo
Removing account-plugin-windows-live ...
Removing aisleriot ...
Removing apt-transport-https ...
Removing nautilus-share ...
Removing apturl ...
entre outros
Eu teria parado em um sistema real, já que isso deveria ser suficiente para dizer que você está fazendo algo errado. Mas como este é apenas um sistema de teste, eu continuei.
Minha lista completa está aqui: Ubuntu Pastebin
Você pode encontrar uma lista no seu sistema em /var/log/apt/term.log
Eu copiei isso para uma unidade externa e imprimi-lo.
Quando reiniciei o Unity, tive que usar Ctrl + Alt + F6 para chegar a um console de texto.
Você pode restaurar cada um deles com
sudo apt-get install package
substituindo o pacote por cada um dos nomes dos pacotes. Eu tentei alguns e parece que está funcionando, mas você vai ter alguns erros "este pacote já está instalado", pois a instalação de um pacote pode puxar outros como dependências para que ele já esteja instalado quando você pedir para instalá-lo.
Provavelmente será mais fácil inicializar com um DVD ou pendrive ao vivo, copiar seus arquivos pessoais e depois reinstalar do que colocar manualmente todos os pacotes de volta. Isso é o que eu estaria fazendo se tivesse acontecido comigo.