LOL, they are sister error messages and one of the most feared ones in mySQL.
What you did was right, but there's a little bit more to it. Before you do anything else, remove the changes you made to the config.inc.php file and remove the password you put in and make it the way it was before. Then if you have access to the server or the mySQL admin program, then edit the my.ini file and then change
#Use old password encryption method (needed for 4.0 and older clients).
old_passwords
# The TCP/IP Port the MySQL Server will listen on
port=3306
Save the file and close it and then connect to the mySQL server and then change the password from (none) to something else.
Now edit the config.inc.php file to make the following changes:
$cfg['PmaAbsoluteUri'] = 'localhost/phpmyadmin/';
$cfg['Servers'][$i]['user'] = 'root'; // MySQL user
$cfg['Servers'][$i]['password'] = 'your new password'; // MySQL password
and change the auth_type back to 'config'. That should fix your problem.
EDIT: Be warned that the changes will take effect only at the next restart of Apache and mySQL.