I received the above error when using the MySql Connector to connect to a database that’s hosted at my hosting provider. Oddly enough, I could connect to the server with the MySql Workbench just fine with the password (and also, the MySql connector worked just fine if it was run from my site on the same domain). The only thing I could think of was that it was enforcing stricter rules when using the connector off the domain.
Anyway, to fix it I ran this SQL from the MySql Workbench (this could be run from any method that allows you to connect and run SQL, say if your provider has a web interface):
SET PASSWORD for <my username>=PASSWORD('<new password here>')