mysql_upgrade fails with "Access denied"

[Grant]

I'm trying to run mysql_upgrade but I get:

# mysql_upgrade
Looking for 'mysql' as: mysql
Looking for 'mysqlcheck' as: mysqlcheck
Running 'mysqlcheck' with connection arguments: '--port=3306'
'--socket=/var/run/mysqld/mysqld.sock'
mysqlcheck: Got error: 1045: Access denied for user 'root'@'localhost'
(using password: NO) when trying to connect
FATAL ERROR: Upgrade failed

I've also tried specifying my root password with --password and also
specifying -u mysql but it still fails with error 1045.  My
/etc/passwd file looks like there is no password for user mysql.  What
else should I try?

- Grant