Per prima cosa fai un backup della tua directory /var/lib/mysql/ solo per sicurezza.
sudo mkdir /home/<your username>/mysql/
cd /var/lib/mysql/
sudo cp * /home/<your username>/mysql/ -R
Quindi elimina MySQL (questo rimuoverà php5-mysql e phpmyadmin così come un certo numero di altre librerie, quindi preparati a reinstallare alcuni elementi dopo questo.
sudo apt-get purge mysql-server-5.1 mysql-common
Rimuovi la cartella /etc/mysql/ e il suo contenuto
sudo rm /etc/mysql/ -R
Quindi controlla che i tuoi vecchi file di database siano ancora in /var/lib/mysql/ se non lo sono, copiali di nuovo nella cartella, quindi chown root:root
(eseguili solo se i file non ci sono più)
sudo mkdir /var/lib/mysql/
sudo chown root:root /var/lib/mysql/ -R
cd ~/mysql/
sudo cp * /var/lib/mysql/ -R
Quindi installa il server MySQL
sudo apt-get install mysql-server
Infine reinstalla tutti i pacchetti mancanti come phpmyadmin e php5-mysql.