Assuma os privilégios de superusuário primeiro seguindo os comandos.
sudo -i
lhe dará acesso root.
O seguinte funcionou para mim:
apt-get -f install -o Dpkg::Options::="--force-overwrite"
E seguido por:
apt-get purge mysql\*
rm -rf /var/lib/mysql
rm -rf /etc/mysql
dpkg -l | grep -i mysql
apt-get clean
apt-get aut
updatedb
apt-get install mysql-client-core-5.5 mysql-client-5.5 mysql-common mysql-server-5.5
Para o uso do mysql5.6 abaixo
apt-get install mysql-client-core-5.6 mysql-client-5.6 mysql-server-5.6
Certifique-se de fazer backup de todos os dados, pois isso excluirá tudo.
Eu encontrei esta solução aqui