Verifique se o pacote mysql-server-5.1 foi desinstalado, parece que ele pode persistir após a atualização. Eu tive o mesmo erro e tive que remover o servidor MySQL 5.1 e 5.5 e reinstalá-lo.
Primeiro faça um backup do seu diretório / var / lib / mysql / apenas para estar seguro.
sudo cp -R /var/lib/mysql/ ~/mysql
Em seguida, remova o MySQL (isso removerá o php5-mysql e o phpmyadmin, assim como um número de outras bibliotecas, então esteja preparado para reinstalar alguns itens depois disso.
sudo apt-get purge mysql-server-5.1 mysql-common
Remova a pasta / etc / mysql / e seu conteúdo
sudo rm /etc/mysql/ -R
Em seguida, verifique se seus arquivos de banco de dados antigos ainda estão em / var / lib / mysql / se eles não estiverem, copie-os de volta para a pasta e então chown root: root
(só execute estes se os arquivos não estiverem mais presentes)
sudo mkdir /var/lib/mysql/
sudo chown root:root /var/lib/mysql/ -R
sudo cd ~/mysql/
sudo cp * /var/lib/mysql/ -R
Em seguida, instale o servidor mysql
sudo apt-get install mysql-server
Por fim, reinstale todos os pacotes ausentes, como phpmyadmin e php5-mysql.