How do I fix a 1045 error when trying to log into phpMyAdmin?

You can fix this error by reconfiguring your phpMyAdmin credentials to gain access to the MySql database:

sudo dpkg-reconfigure phpmyadmin

This will provide several interactive menus that will allow you to reconfigure the phpMyAdmin package with new credentials.

You could also attempt to manually reconfigure the credentials for the 'phpmyadmin' user from within MySql by taking the following steps:

1) Log into MySql as root:
mysql -u root -p

2) You can make sure that the 'phpmyadmin' user exists by running:
SELECT User FROM mysql.user;

3) Switch to the appropriate MySql database:
use phpmyadmin;

4) Set a new password for the 'phpmyadmin' user:
update user set password=PASSWORD('your_new_password') where User='phpmyadmin';

But the user table is in mysql database, right?

then for step 3 should be

use mysql;