Prova a seguire il comando nella shell (l'utente root qui è l'utente root mysql, non il root di sistema)
sudo mysql_upgrade -u root -p
sudo service mysql restart
Assicurati di riavviare mysql dopo averlo eseguito (Tutto merito a @Mikepote nei commenti.)
