Ubuntu :: Cannot Login As Mysql

I'm having problems with a mysql install on a ubuntu server edition.

I forgot the mysql root password(or maybe it's always been screwy), so I attempted to reset the root password using this:

Code:
sudo dpkg-reconfigure mysql-server-5.0

However this did not work.

So I decided to run

Code:
sudo apt-get purge mysql-server-5.0 && sudo apt-get install mysql-server-5.0

And re-entered the root password and again I still can't login!

This is the error I keep getting.

Code:
ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)

Is there any further steps I can do to wipe this crappy mysql install?