First make a backup of your /var/lib/mysql/ directory just to be safe.
sudo mkdir /home/<your username>/mysql/
cd /var/lib/mysql/
sudo cp * /home/<your username>/mysql/ -R
Next purge MySQL (this will remove php5-mysql and phpmyadmin as well as a number of other libraries so be prepared to re-install some items after this.
sudo apt-get purge mysql-server-5.1 mysql-common
Remove the folder /etc/mysql/ and it's contents
sudo rm /etc/mysql/ -R
Next check that your old database files are still in /var/lib/mysql/ if they are not then copy them back in to the folder then chown root:root
(only run these if the files are no longer there)
sudo mkdir /var/lib/mysql/
sudo chown root:root /var/lib/mysql/ -R
cd ~/mysql/
sudo cp * /var/lib/mysql/ -R
Next install mysql server
sudo apt-get install mysql-server
Finally re-install any missing packages like phpmyadmin and php5-mysql.