MySql >= 4.1 Client does not support authentication protocol

If you upgrade your MySql server to >= 4.1 you might get the following error:
- Client does not support authentication protocol requested by server; consider upgrading MySQL client

This happens because the latest versions of MySql uses a new format for the password (it's a longer hash). In order for old clients to continue to use the newer server, you have to set the passwords on the server to their old format or upgrade your client. Because upgrading the client can sometimes be a pain, it's often easier to just update the passwords to the old format on the server.

Run mysql and login as root:

mysql -u root -p

Then, paste the following command, editing as necessary, to change the password of the user to the old format.

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

After you have set the passwords to the old format, flush the tables.
flush privileges;

Then exit the mysql client with "quit" and you are set.