Você corrompeu seus pacotes que vejo. Você disse que cancelou a instalação do servidor MySQL, que é o pacote mysql-server-5.1
.
Tente limpar sua configuração do MySQL e reinstalá-la:
sudo rm -rf /etc/mysql /var/lib/mysql
sudo apt-get install mysql-server-5.1
Observe que o primeiro comando limpa configurações e senhas anteriores do banco de dados MySQL, incluindo o próprio banco de dados MySQL. Se você acabou de instalar o servidor (como eu posso fazer a partir de sua pergunta), isso não é um problema.
Como o SpamapS notou, você pode usar o recurso de limpeza do apt para se livrar do servidor MySQL e suas configurações. Os comandos para limpeza e instalação são os seguintes:
sudo apt-get --purge remove mysql-server-5.1
sudo apt-get install mysql-server-5.1