Experimente a seguinte sequência de comandos:
sudo apt-get remove mysql-server-core-5.5 mysql-server-5.5 mysql-server
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install mysql-server
A instalação de apenas mysql-server
(sem o sufixo 5.5) deve funcionar.