A solução é simples. Você não está usando o Ubuntu 16.04 que tem o gerenciador de aplicativos gnome. O gerenciador de aplicativos padrão no Ubuntu é lento e com bugs. Atualize para o ubuntu 16.04.
Se você não gostou dessa solução, tente usar aptitude . Primeiro você precisa instalá-lo usando sudo apt-get install aptitude e depois instalar os pacotes usando sudo aptitude install wine . Ele tentará automaticamente resolver o problema. Leia mais sobre isso digitando man aptitude no terminal depois de instalá-lo.
Se nada funcionar, tente digitar sudo apt-get -f install <PACKAGE NAME> . Então diga o que exatamente acontece em cada caso.