I ended up solving this last night after pulling most of my hair out. It appears that the issue was resolved by setting an SPN up binding the CRM service account to the FQDN URL for my server (I intend for it to be public facing and so this is the externally
available URL) and biding the URL to the machine account itself:
setspn -A HTTP/CRM.MYDOMAIN.COM MYDOM\CRM_SERVICE
setspn -A HTTP/CRM.MYDOMAIN.COM MYCRMSERVER$
The system log was showing Kerberos failures for the machine account every time I tried to connect which is what sent me in this direction.