Cannot connect to MySQL: Client does not support authentication protocol requested by server

I ran into a problem on a client site running cPanel. One our our web apps was spitting out the following error:

1 2	Script Error Cannot connect to MySQL: Client does not support authentication protocol requested by server; consider upgrading MySQL client

From inside MYSQL, Run the following on the affected DB:

1	SET PASSWORD FOR user@localhost = OLD_PASSWORD('replacemepasswd');