Hey there, Majesk!
It sounds like the host that's being used isn't allowing the outbound call to be made. Therefore, MailChimp isn't able to verify the API key and producing that error. Unfortunately, in this case, your best bet would probably be to get in touch with the host to see if they're blocking any sort of outbound traffic or calls.
Additionally, you might be able to test the connectivity (and API Key) by setting up a local installation of WordPress and using the same API Key.
If you do have any other questions, please don't hesitate to give us a shout!