mysql_tzinfo_to_sql /usr/share/zoneinfo | mysql -u root -p mysql
ERROR 1698 (28000): Access denied for user 'root'@'localhost'

The Cause

SELECT user, password 
FROM user
WHERE User = 'root';
| User        | Password |
| root        | invalid  |

So that looks like our answer.

The Solution

SET PASSWORD FOR 'root'@localhost = PASSWORD("myReallyStrongPwd");

Running that (with a different password) did the trick.

So if getting the above error, perhaps this will help.