Incompatibilidad MySQL PHP

La cuenta MySQL que está utilizando probablemente tenga una contraseña antigua de 16 caracteres (hash).
Puede probar eso con un cliente MySQL (como HeidiSQL, el cliente de la consola MySQL o cualquier otro cliente) y una cuenta que tenga acceso al mysql .user mesa. Si el campo Contraseña contiene 16 caracteres, es una contraseña antigua y mysqlnd no puede usarlo para conectarse al servidor MySQL.
Puede establecer una nueva contraseña para ese usuario con

SET PASSWORD FOR 'username'@'hostmask' = PASSWORD('thepassword')

consulte dev_mysql_set_password

editar:
También debe verificar si el servidor está configurado para usar/crear contraseñas antiguas de forma predeterminada .

edit2:
Ejecute la consulta

SELECT
  Length(`Password`),
  Substring(`Password`, 1, 1)
FROM
  `mysql`.`user`
WHERE
  `user`='username'

en el servidor 5.0.22 (el que está "fallando"). Reemplazar username por la cuenta que está usando en mysql_connect().
¿Qué devuelve eso?