Eu enfrentei um problema muito semelhante. A maneira como resolvi isso é limpar os pacotes do MySQL no APT e, em seguida, instalar novamente.
sudo apt-get purge mysql-server-5.5 mysql-common
sudo apt-get install mysql-server
Pacotes como mysql-common e mysql-client são instalados como dependências.
O purge parece funcionar no meu caso, pois eu estava testando várias configurações de instalação (encadeada, pré-fork, etc), e alguns arquivos de configuração eram apenas obsoletos, permanecendo por aí. O purge limpa tudo e redefine a configuração.
Note que achei a lista de pacotes para remover usando dpkg -l | grep mysql , onde rc e ii pacotes provavelmente precisam ser limpos (funcionou no meu caso).