Error:
shell> mysql
Client does not support authentication protocol requested
by server; consider upgrading MySQL client
To solve this problem, you should use one of the following approaches:
Upgrade all client programs to use a 4.1.1 or newer client library.
 
When connecting to the server with a pre-4.1 client program, use an account that still has a pre-4.1-style password.
 
Reset the password to pre-4.1 style for each user that needs to use a pre-4.1 client program. This can be done using the 
SET PASSWORD statement and the 
OLD_PASSWORD() function:
 
mysql> SET PASSWORD FOR
    -> 'some_user'@'some_host' = OLD_PASSWORD('newpwd');
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.
 
Tell the server to use the older password hashing algorithm:
- 
 
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.
 
 
 
 
 
Note
In older versions of PHP, the 
mysql extension does not support the authentication protocol in MySQL 4.1.1 and higher. This is true regardless of the PHP version being used. If you wish to use the 
mysql extension with MySQL 4.1 or newer, you may need to follow one of the options discussed above for configuring MySQL to work with old clients. The 
mysqli extension (stands for "MySQL, Improved"; added in PHP 5) is compatible with the improved password hashing employed in MySQL 4.1 and higher, and no special configuration of MySQL need be done to use this MySQL client library. For more information about the 
mysqli extension, see 
http://php.net/mysqli.
 
 
It may also be possible to compile the older 
mysql extension against the new MySQL client library. This is beyond the scope of this Manual; consult the PHP documentation for more information. You also be able to obtain assistance with these issues in our 
MySQL with PHP forum.
 
From: http://dev.mysql.com/doc/refman/5.0/en/old-client.html