ANSWER:

I had this same problem on a Debian install on a VPS (Gigatux). The command “dpkg-reconfigure mysql-server-5.1″ would let me set/reset the root MySQL password but authentication would still fail with the error “Access denied for user ‘root’@'localhost’”

Ultimately my issue was caused by not having the correct permissions on the /tmp folder when MySQL was installed. My /tmp folder had the permissions “drwxr-xr-x” when it should have been “drwxrwxrwt”. Even after setting the correct permissions I could not fix the issue, I had to have the permissions set BEFORE I installed MySQL.

I have documented my experience in more detail at http://www.craigdodd.co.uk/2012/01/missing-root-account-in-mysql/ if anyone is interested.

by Craig Dodd from http://superuser.com/questions/420772