Surely this has gott to be an 'access' issue. Try explicitly granting rights to the user on the specific database in question.
-> there is one other thing, how r u trying to access the database, I believe that there was a change on the way that MySQL handles passwords, I had problems with PHP and MySQL, becuase PHP didn;t support the new version passwords on MySQL. There is a configuration option in the mysql conf file to endable 'old passwords' I think.