Tente seguir o comando no shell (o usuário root aqui é o usuário root do mysql, não o root do sistema)
sudo mysql_upgrade -u root -p
sudo service mysql restart
Certifique-se de reiniciar o mysql depois de executar isso (todos os créditos para @Mikepote nos comentários.)
