Could be that the new PW is hashed under the new hashing algorithm used by the latest versions of MySQL, but that the webserver has an older version of MySQL Client API that can't handle the new hashing algorithm. I'm fighting with my employer's webhost over the same issue right now. The solution is to reset the DB PW to use the old-style hashing algorithm.

More info:
http://dev.mysql.com/doc/refman/5.0/en/old-client.html

Good luck!