MySQL: Client does not support authentication protocol

MySQL 4.1 and later uses a new authentication protocol which is not compatible with the libraries that php 4 uses. 

There are two options:

  1. The way around this is to reset the password for the needed accounts to use pre-4.1 style.
    mysql> SET PASSWORD FOR
        -> 'some_user'@'some_host' = OLD_PASSWORD('newpwd');
    
    Alternatively, use UPDATE and FLUSH PRIVILEGES:

    mysql> UPDATE mysql.user SET Password = OLD_PASSWORD('newpwd')
        -> WHERE Host = 'some_host' AND User = 'some_user';
    mysql> FLUSH PRIVILEGES;
    
    Substitute the password you want to use for "newpwd" in the preceding examples. MySQL cannot tell you what the original password was, so you'll need to pick a new one.
     
  2. Tell the server to use the older password hashing algorithm:
     
    Start mysqld with the --old-passwords option. Assign an old-format password to each account that has had its password updated to the longer 4.1 format. You can identify these accounts with the following query:

    mysql> SELECT Host, User, Password FROM mysql.user
        -> WHERE LENGTH(Password) > 16;
    

    For each account record displayed by the query, use the Host and User values and assign a password using the OLD_PASSWORD() function and either SET PASSWORD or UPDATE, as described earlier.

For more info, please see this article on the mysql site:
http://dev.mysql.com/doc/mysql/en/old-client.html