Si por alguna razón (tanto en windows como en linux) utilizamos un cliente mysql 4 con un mysql server 4.1 que tiene activado el nuevo protocolo de autenticación, cada vez que creemos un usuario vamos a recibir el siguiente error al intentar conectar:

#1251 – Client does not support authentication protocol requested by server; consider upgrading MySQL client

Existen tres soluciones para este problema:
1- Actualizar el cliente de MySQL.
2- Establecer manualmente la contraseña del usuario a utilizar con el siguiente comando: SET PASSWORD FOR ‘usuario’@'localhost’ = OLD_PASSWORD(‘contraseña’);
3- Editar el archivo de configuración de MySQL (my.conf o my.ini) y en la sección de MySQL agregar: old_passwords 1

Ejemplo:
[mysqld]
old_passwords=1

Espero que haya sido de utilidad!