If you attempt to connect to a MySQL 4.1.x server from a MySQL 4.0.x client you may receive the following error:
#1251 - Client does not support authentication protocol requested by server; consider upgrading MySQL client
To fix the problem, first make sure that you have no usernames that are longer than 16 characters:
SELECT Host, User, Password FROM mysql.user WHERE LENGTH(Password) > 16
Now you may update the password for the user to the old style passwords:
SET PASSWORD FOR 'root'@'localhost' = OLD_PASSWORD('newpasswd');
For more information see: Password Hashing in MySQL 4.1