I also had the same problem with this but on Windows after upgrading to MySQL 5.5 from MySQL 5.1. I already tried changing, creating, and resetting password mentioned in here, here, here, and here, no clue. I still get the same error:
ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)
I'm able to connect normally, show all databases, do selects and inserts, create and add users, and but when it comes to GRANT, I'm screwed up. Those access denied error shows up again.
I managed to solve this problem by fixing the privileges by the following command on the MySQL server bin/ directory as mentioned in here:
C:\MySQL Server 5.5\bin> mysql_upgrade
Then, the problem gone away. I hope this solution works on Linux too since usually MySQL provide the same command both on Linux and Windows.