Thanks Ray. I've been back and forth with the hosting company too. They have been trying a few things, but no luck yet. They set some permissions, and had me change the MySQL Server in the settings from 'localhost' to the IP address of the server. They've had me install Telnet to try to connect, and I've just given them the output from that, which was:
Connected to no-rdns.speedyservers.com.
Escape character is '^]'.
5.6.45cPDFq)u??~"'@K8wnA;Cmysql_native_passwordConnection closed by foreign host.