Try reading this: link
MySQL introduced longer password hashes in (i think) version 4.1, and your server probably still uses them (check for 16 byte password hashes in your mysql user table). Newer versions use longer password hashes. Your server supports both, but your client (php) seems to support only new ones in this version (and on).
If it's possible, use the solution from the link in the first line, and set your password again with the new hash, but beware, if you're using any other (old) clients which rely on old passwords, compatibility might break. Also try looking for old-password support for MySQL in PHP, but i'm not sure about it.