Isso funcionou para mim:
apt-get purge mysql-server
apt-get purge mysql-common
rm -rf /var/log/mysql
rm -rf /var/log/mysql.*
rm -rf /var/lib/mysql
rm -rf /etc/mysql
# and then:
apt-get install mysql-server --fix-missing --fix-broken
Embora também remova todas as dependências do mysql.
E também excluirá os bancos de dados existentes, faça o backup primeiro!
Fonte .