Answer to my own question
After a great deal of effort I figured out that the hosting company had never installed the client mysql service, and they couldn't figure it out, so I installed it myself. My above post I had hacked out a solution by connecting everything to the Plesk MySQL server which was not a real solution.
Just in case this happens to others here is what I did to install the mysql client server,(if you look at the services and the MySQL server doesn't exist, try this):
In the folder C:\SWsoft\Install\%your plesk build date%\ you will notice two key files. AdminMySQL.msi and ClientMySQL.msi. These are both preconfigured instances of mysql. The AdminMySQL.msi is used exclusively by Plesk to store Plesk's data about clients, users, domains, etc. It installs into the directory C:\SWsoft\Plesk\MySQL and runs as Plesk SQL Service in the services panel. The second ClientMySQL.msi installs a fully seperate mysql server in the C:\Program Files (x86)\MySQL\MySQL Server 4.1\ directory (or something quite close to that). This is the database that should be used by clients and client applications. Don't bother configuring it as it should already be set up correctly.
It seems to make the server more secure to have them seperate, and would make Plesk easier to upgrade at a later point. The problem with our VPS was that the ClientMySQL.msi installed was never run and the client mysql was never installed. This really confused me. It might be good as well to add the path to the client mysql bin so that it's easier to access.