Muitos pacotes têm outros pacotes de que dependem para trabalhar, (apropriadamente) chamados de "dependências". Estes são instalados automaticamente, sendo a única reação do usuário confirmar a instalação do pacote base. Os pacotes que você vê marcados para remoção são essas dependências.
O comando ppa-purge exclui o repositório especificado (WINE, neste caso), quaisquer pacotes instalados disponíveis a partir dele e quaisquer dependências para esses pacotes.
Execute sudo apt-get install -f e sudo dpkg --configure -a antes de executar o comando ppa-purge novamente. Em seguida, execute sudo apt-get install -f para garantir que tudo esteja OK.
EDITAR : Acabei de notar que existem alguns pacotes de sistema que você já removeu. A opção PGA Purge pode não ser boa. Em vez disso, tente executar sudo apt-get install -f e, em seguida, sudo apt-get remove wine-* .