remover o mysql-server não funciona porque o mysql-server é apenas um meta-pacote que depende da versão específica do servidor
apt-get remove --purge 'mysql-.*'
ou
apt-get remove --purge 'mysql-server.*'
fará o truque.
Eu pensei em compartilhar minha pergunta aqui e então responder, já que parece haver muitas pessoas presas na minha posição - mas nenhuma resposta definitiva. O problema é que, se você remover o mysql-server, ele não limpará os arquivos de configuração e banco de dados, então, se você de alguma forma os tiver parafusado, a instalação novamente não os substituirá. Portanto, parece haver muitas pessoas perguntando "como remover completamente o mysql-server, para que eu possa reinstalar um novo?" - todos respondem com apt-get remove --purge mysql-server - não sei por que, mas isso não é totalmente desinstalado. Minha resposta segue ...
Isso funcionou para mim (eu também tentei instalar a v5.0, mas isso piorou as coisas):
apt-get remove --purge mysql-server-5.0 mysql-common mysql-client-5.0 \
mysql-server-5.1 mysql-client-5.1 mysql-server mysql-client
apt-get install mysql-server
Acho que a chave aqui é remover mysql-common - mas não tenho certeza. Por favor, tente isso e deixe seus comentários.
Eu tive alguns problemas com isso. Mesmo depois de remover todos os pacotes do servidor, existem alguns arquivos de configuração instalados por mysql-common , que é uma dependência de libmysqlclient .
Tente usar dpkg -S /etc/mysql para ver quais pacotes estão instalando esses arquivos.
Você também pode usar o dpkg -P para conseguir isso
Da página de manual do dpkg
-P or --purge removes everything, including configuration files.