Isso aconteceu comigo, mas foi assim que, depois de fazer um sudo apt-get update , de alguma forma não obteve a versão mais recente do mysql-server , apenas do mysql-server-core . Eu sugeriria primeiro fazer outro sudo apt-get update e depois prosseguir com a instalação do pacote
sudo apt-get install mysql-server
Se isso não funcionar, faça uma reinstalação:
sudo apt-get install --reinstall mysql-server
E se isso não funcionar, basta purge do pacote mysql-server-core package e instalar mysql-server novamente.
sudo apt-get purge mysql-server-core mysql-server-core-5.5
sudo apt-get install mysql-server
E se isso não funcionar, enlouqueça com:
sudo apt-get clean
sudo apt-get autoclean
sudo apt-get purge mysql-server*
sudo apt-get install mysql-server
Como último recurso, eu limparia, reinicializaria e instalaria.