Error de conexion

[Elalux]

Saludos maestros, he aqui mi caso.

Al intentar hacer la conexión a MySQL me da el siguiente error extraño (al menos para mí):

----------------------------------------
Warning: mysql_connect(): Client does not support authentication protocol requested by server; consider upgrading MySQL client in /home/revista/public_html/conexion.php on line 2
I cannot connect to the database because: Client does not support authentication protocol requested by server; consider upgrading MySQL client
-----------------------------------------

A continuación la cadena de conexión:

----------------------------------
$dbh=mysql_connect ("localhost", "usuario", "password") or die ('I cannot connect to the database because: ' . mysql_error());
mysql_select_db ("base_datos");
-----------------------------

Lo mas extraño es que la cadena de conexión la he revisado no menos de 10 veces y esta bien, incluso la pruebo en otro server y se conecta sin ningú problema, sinceramente es la primera vez que veo este error, alguien me podría echar una manita, agradezco desde ahora cualquier ayuda.

Una cosita mas, corri la función phpinfo en ambos server y las características de MySQL son idénticas, al menos no encontre ninguna diferiencia.

Saludos.