Problema.

mysql_upgrade
Looking for 'mysql' as: mysql
Looking for 'mysqlcheck' as: mysqlcheck
FATAL ERROR: Upgrade failed

Solución: Arrancar el servicio y actualizar como root.

service mysqld start
mysql_upgrade -u root -p