The same as Ulrich Metzger, after upgrading my machine to Ubuntu 16.04 and Mysql-server-5.7, I couldn't log in with root because the
plugin column changed.
My problem was not solved with
sudo dpkg-reconfigure mysql-server-5.7 + removing + purging + cleaning.
I had to stop the mysql service:
# sudo service mysql stop
Then restart the mysql daemon with the
# sudo mysqld_safe --no-grant-tables &
Then in another terminal, enter the mysql console (which now doesn't need authentication) with the command
mysql, and update the password and plugin columns via a SQL UPDATE:
WHERE User='root' AND Host='localhost';
Finally, kill the
mysqld_safe command, restart mysql service and connect to mysql normally:
# sudo service mysql start