Completely locked out of MySQL!

You'll need to reset the root password using mysqladmin from the command line.

mysqladmin password your-new-root-password

Might need to specify the root user explicitly:

mysqladmin -u root password your-new-root-password

Might also help to flush privileges from mysqladmin:

mysqladmin flush-privileges

Then you might need to grant all privileges back to root. Not sure if this is necessary.

GRANT ALL PRIVILEGES ON *.* TO root@localhost IDENTIFIED BY 'your-new-password';

http://dev.mysql.com/doc/refman/5.0/en/resetting-permissions.html

Make sure that the mysqld process is killed before you try to do the reset. Try logging into the mysql client as you say yuo can in your question.