USE THIS AS A LAST RESORT METHOD, YOU WILL LOSE ALL YOUR MYSQL DATA

sudo apt-get --purge remove mysql-server mysql-common mysql-client

sudo apt-get install mysql-server mysql-common mysql-client

In the next step be sure to chance the your-new-password with the password you want!

mysqladmin -u root password your-new-password
sudo /etc/init.d/mysql restart

mysql -u root -p