Eu sugeriria usar o apt-get autoremove e depois disso é feito usar synaptic ou algo para consertar dependências quebradas. Não tenho certeza se isso vai funcionar, mas é o que eu tentaria. eu removi o vinho e usei o autoremove apt-get no meu 15.10 e funcionou bem. talvez você precise fazer uma atualização do sistema ou algo assim. uma coisa que eu não fiz é sudo apt-get purge eu costumo usar synaptic um clique direito e selecione marca para remoção completa que tinha me instalar uma versão genérica de somehting não consigo me lembrar agora, mas depois eu auto removei a maioria das mesmas coisas que você fez e ele me pediu para reiniciar e inicializou muito bem.