Please try this first:
apt-get purge mysql-server mysql-client mysql-common mysql-client-5.5 mysql-server-5.5
then reinstall mysql server.
If this doesn't work only then try the following:
sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get remove --purge mysql*
followed by :
sudo apt-get autoremove
sudo apt-get autoclean
If you want to preserve the configuration files then omit the '--purge' part in the first line.
Then to reinstall:
sudo apt-get update
sudo apt-get install mysql-server
warning: I never had to use the second method myself. Make a decent backup of your databases, if you have any, before trying this.