Eu tive o mesmo problema, provavelmente resultante da instalação / teste / remoção de muitos softwares. Eu resolvi isso limpando e reinstalando o mysql-server.
apt-get purge mysql-common
Claro, cuide dos seus dados do mysql antes de limpá-los. Não tenho certeza se seus dados sobreviveriam à linha de comando acima. Eu não me importava com meus dados, porque era apenas lixo que eu usava para testes.
Espero que isso ajude.
TomTomTom