Como você pode ver na página wiki que você vinculou, o nome do pacote não é wine , escolha um dos três nomes de pacotes listados e seu comando provavelmente funcionará melhor:
- winehq-stable
- winehq-devel
- winehq-staging
Ou apenas tente: sudo apt-get purge winehq*
Você também pode executar sudo apt-get autoremove para limpar.