[mysql] MySQL ERROR 1045 (28000): Access denied for user 'bill'@'localhost' (using password: YES)

For me, this problem was caused by a new feature of MySQL 5.7.2: user entries are ignored if their plugin field is empty.

Set it to e.g. mysql_native_password to reenable them:

UPDATE user SET plugin='mysql_native_password' WHERE user='foo';
FLUSH PRIVILEGES;

See the release notes for MySQL 5.7.2, under «Authentication Notes».

For some reason (maybe because my pre-4.1 password hashes were removed), the mysql_upgrade script didn't set a default plugin value.

I found out by noticing the following warning message in /var/log/mysql/error.log:

[Warning] User entry 'foo'@'%' has an empty plugin value. The user will be ignored and no one can login with this user anymore.

I post this answer here to maybe save someone from using the same ridiculous amount of time on this as I did.