Incompatibilité MySQL PHP

Le compte MySQL que vous utilisez a probablement un ancien mot de passe de 16 caractères (hachage).
Vous pouvez le tester avec un client MySQL (comme HeidiSQL, le client de la console MySQL ou tout autre client) et un compte qui a accès au mysql .user table. Si le champ Mot de passe contient 16 caractères, c'est un ancien mot de passe et mysqlnd ne peut pas l'utiliser pour se connecter au serveur MySQL.
Vous pouvez définir un nouveau mot de passe pour cet utilisateur avec

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

voir dev_mysql_set_password

edit :
Vous devez également vérifier si le serveur est défini sur utiliser/créer d'anciens mots de passe par défaut .

edit2 :
Veuillez exécuter la requête

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

sur le serveur 5.0.22 (celui qui "échoue"). Remplacer username par le compte que vous utilisez dans mysql_connect().
Qu'est-ce que cela renvoie ?