From Birnam Designs Wiki

MySQL versions 4.1 and more recent improved the security of their password storage in the user table. PHP5 is capable of logging in with this, but PHP4 cannot, you will get the error "MySQL client does not support authentication protocol". To update the passwords for a user:

Login to the database as root:

mysql -u root -p

And enter the following SQL, replacing the values as necessary:

UPDATE mysql.user
SET password=OLD_PASSWORD('somepassword')
WHERE user='someuser'
AND host='somehost';

After this command, you will need to flush the privileges to make the update available:

flush privileges;