It has been a while since I have seen this error, I'm not sure that I have ever encountered it on a Linux type OS. Basically the reason you are getting this error is due to the password hashing algorithm that is used by the newer version of MySQL, it is not compatible with the version that was used when your server was setup.
This is something that I think your host would have to control since the fix is to either update the library files to the newer ones, or adjust your db users password to use the old hashing technique. Here is a link to the MySQL page that details this:
old-client.html
