MySQL PHP incompatibility

I have been trying to find a simple fix for this problem. Try this approach. In MySQL type

SELECT Host, User, Password FROM mysql.user;

If your password is sixteen characters, this is because you have used OLD_PASSWORD on your user's or have been running an old version of MySQL. To update type in

UPDATE mysql.user SET Password=PASSWORD('newpass')
  WHERE User='root' AND Host='localhost';
FLUSH PRIVILEGES;

swapping root, localhost and newpass for your user, host and pass respectively. Now when you re-type

SELECT Host, User, Password FROM mysql.user;

Your password should have changed. This fixed it for me.

A more simple solution is to delete the database user and create a new one with the same username and password.

The MySQL account you're using probably has an old 16 character long password (hash).
You can test that with a MySQL client (like HeidiSQL, the MySQL console client or any other client) and an account that has access to the mysql.user table. If the Password field contains 16 chars it's an old password and mysqlnd cannot use it to connect to the MySQL server.
You can set a new password for that user with

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

see dev_mysql_set_password

edit:
You should also check if the server is set to use/create old passwords by default.

edit2:
Please run the query

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

on the 5.0.22 server (the one that's "failing"). Replace username by the account you're using in mysql_connect().
What does that return?

Your database server is set to use old passwords by default. The error message you get is mysqlnd seeing a database that can support the new (safer) authentication but refuses to do so. In such a case, mysqlnd aborts the connection and refuses to work.

Make sure your my.cnf does not have

old-passwords = 1 

After you comment out that setting from my.cnf (or remove it from where else it might be set), and restart your server, make sure to re-set your password using the command VolkerK describes, otherwise you won't be able to log in.