Comment 14 for bug 542543

I got it fixed, thanks to post #4 on this thread: http://ubuntuforums.org/showthread.php?t=1836919

Start your mysql client as shown below:

    mysql -u debian-sys-maint -p

In another terminal, 'cat' the file /etc/mysql/debian.cnf (you'll have to 'sudo cat' it). That file contains a password; paste that password in the first terminal when prompted for it. Then execute the following commands at the 'mysql>' prompt:

    grant all privileges on *.* to 'root'@'localhost' identified by 't1g3r' with grant option;
    flush privileges;

That did it for me!