Este error se produce cuando una librería antigua de acceso mysql intenta acceder a una nueva versión 4.1.1 o superior de MySQL. Aparte de actualizar la librería (obvio) también se puede usar la siguiente sentencia para el usuario con el cual estamos intentando acceder:

SET PASSWORD FOR 'usuario'@'host' = OLD_PASSWORD('password_elegida');

Muy buen dato