Client does not support authentication protocol requested by server; consider up

Hi my understanding of PHP and MySQL is very basic, I’m installing WSB onto a windows HEML server but connecting remotely via IP address to a MySQL server that I know WSB works on without any problems, when I run WBS locally (bear in mind that this is a Linux server), however when I try to install WBS onto the windows HEML server I get the error message below. Step 1 and 2 are all ok, the error message appears at the top of the install page.

Error: Database host name, username and/or password incorrect. MySQL Error:
Client does not support authentication protocol requested by server; consider upgrading MySQL client

Setting are:
PHP Version > 4.1.0 (windows)
MySQL Version > 5.0 (Linux)

WSB has to run on the server because it needs to running with some other website elements that only work with ASP and SQL for an ecommerce package

Any help would be really appreciated, Iv already spoken to the server engineer and they wont install Apache on it.