Authentication Protocol Problems
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: