MySQL 4.1 and up uses an authentication protocol based on a password hashing algorithm that is incompatible with that used by older clients. If you upgrade the server to 4.1, attempts to connect to it with an older client may fail with the following message:
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:
mysql> SET PASSWORD FOR -> some_user@some_host = OLD_PASSWORD('newpwd');
References: