mysqli, the recommended PHP interface to mysql, will not authenticate with mysql servers using old (16-bit hash) passwords. This is the message you see:
PHP Warning: mysqli::mysqli(): (HY000/2000): mysqlnd cannot connect to MySQL 4.1+ using the old insecure authentication. Please use an administration tool to reset your password with the command SET PASSWORD = PASSWORD('your_existing_password'). This will store a new, and more secure, hash value in mysql.user. If this user is used in other scripts executed by PHP 5.2 or earlier you might need to remove the old-passwords flag from your my.cnf file
Here's the solution, as long as you have MySQL DB admin rights:
Caveat emptor: What you are doing here runs the risk of denying access to your database, to the point of not being able to access the mysql at all. What I've explained above did the job for me, but don't blame me if it doesn't work for you! If you have the option, do a test run on a non-production server first.