The same as Ulrich Metzger, after updgrading my machine to Ubuntu 16.04 and Mysql-server-5.7, I couldn't log in with root because of
plugin column changed in mysql database.
sudo dpkg-reconfigure mysql-server-5.7 command and removing, purging and cleaning did not solve my problem.
I had to stop mysql service
# sudo service mysql stop
Start mysql daemon with no
# sudo mysql_safe --no-grant-tables &
Then in another terminal, enter mysql (which do not have anymore authenfication) with command
mysql, and update password and plugin columns via a sql UPDATE
WHERE User='root' AND Host='localhost';
mysql_safe command, restart mysql service and connect to mysql normaly
# sudo service mysql start