#1045 - Access denied for user 'root'@'localhost' (using password: YES)

I first changed the root password running mysql at a prompt with

mysql -u root -p

Update password:

UPDATE mysql.user SET Password=PASSWORD('MyNewPass') WHERE User='root';

Edited line in the file config.inc.php with the new root password:

$cfg['Servers'][$i]['password'] = 'MyNewPass'

Stop and re-start mysql service (in Windows: mysql_stop.bat/mysql_start.bat)

and got phpMyAdmin to work!

EDIT 2017: for MySQL=5.7 use authentication_string in place of Password (see this answer):

UPDATE mysql.user SET authentication_string=PASSWORD('MyNewPass') WHERE User='root';