The above error message most likely occurs when users change password in one environment (via command line or phpmyadmin) and do not see the changes reflect in other OR if they have forgotten the password that is being set for the environment in question.
Following command should help you set/change MySQL password
$ mysql -u root -p
mysql> use mysql;
mysql> show tables;
mysql> desc user;
mysql> update user set password=PASSWORD(‘mypassword’) where User=’root’;
mysql> flush privileges;
Now you need to enter the new password for the user ‘root’ to gain access to mysql.
Point to note:
Prior to MySQL 4.1 PASSWORD function returns 16 byte string and in later versions it returns 41 byte string. In later versions, passwords begin with “*”. When users migrate databases from one version to other there are chances for the application to break if this factor is not considered. In later versions, if users want to still use the old form of password hashing there is a function “OLD_PASSWORD” available to them.