As of version 4.1 of MySQL, a new algorithm is used for handling user passwords. While this change is more secure, it has led to many confusing problems, including the "Client does not support authentication protocol" error. This error is caused by using an older client to connect to a newer installation of MySQL. I've seen it most frequently when using PHP's older MySQL functions (mysql_*) to connect to MySQL 4.1 or 5.
There are several solutions to this problem:
Use an older version of MySQL. This is an easy option, although not ideal.
Tell the newer version of MySQL to behave, with respect to the authentication protocol, like the old version. To do so, start the server with the --old-passwords setting. You can opt for this within the MySQL Administrator, too (Figure A.12).
Figure A.12. If absolutely necessary, you can tell the MySQL server to use the old-style password algorithm.
Similarly, you could use the old-style password algorithm for just certain users. Update their password within the MySQL monitor by using this command:
SET PASSWORD FOR 'username'@'hostname' = OLD_PASSWORD('thepassword')
The third solution is to upgrade the client. For PHP in particular, this means switching to the new MySQL Improved Extension functions (mysqli_*).