Appointment+ Invalid Credentials

This question was posed earlier by Jess: link to post. The fix he came up with was to change his hosting service to get it to work.

That solution won't work for me. My setup is 100% correct except for one item: my server time is wrong by about 23 minutes. I am trying to correct this issue with my provider, but I am wondering if the credential issue is really a server time issue (which is pretty common).

Has anyone been able to resolve this issue (without relocating to a new host), and is there any other server-related issues that may be causing this credential issue?