I ran into this problem more than enough times, during the last year and I am tired remembering the solution, each and every time. So, I am going to post it here, for my own sake and for the sake of those who may find it here and bless me for being so kind (heh).

Anyway, here it is:

MySQL has changed password hashing mechanism starting from version 4.1 and if you are trying to use any "older client" (including PHP 4 or the pre-last MySQL driver) you will get an error of the type: #1251: Client does not support authentication protocol requested by server; consider upgrading MySQL client.

You thought you were screwed, did not you? :) Not entirely. Those folks @ MySQL are definitely nuts, for changing password hashing, but they are not THAT crazy, after all. They did leave a way out and here it is.

When you add a user, in MySQL 4.11 and newer, with a command like: \ GRANT ALL PRIVILEGES ON dbname.* TO user@localhost IDENTIFIED BY \'secretPassword\';

It will create password entry with new hashing and your "old" client will not be able to authenticate.  But, if you run a command like the following afterwards: \ set password for \'user\'@\'localhost\' = OLD_PASSWORD(\'secretPassword\');

it will update the appropriate entry with the old hashing and everything will just work, even with your poor, old, "stupid" client.