But this message was clearly off because the Server URL and organization were clearly correct.
To troubleshoot, I enabled the Troubleshooting using the CRM Outlook client Diagnostics tool (the way to go about this is described here). Reviewing the trace file I was able to identify the cause of the error i.e. the following text appeared indicating an authentication issue:
Error| Exception : The HTTP request is unauthorized with client authentication scheme 'Anonymous'. The authentication header received from the server was 'Negotiate,NTLM'.
The resolution was simply to enable "Anonymous Authentication" to the CRM web site i.e.: