I have seen many issues lately where Office 365 has connection issues affecting setting up new Outlook profiles, odd certificate popups, seeing delegated email accounts and shared calendars. Turns out it is due to Outlook resolving to the root domain such as domain.com rather than autodiscover.domain.com. This is an issue when hosting providers have mail servers that are listening on that domain and it causes Outlook to get the response and fails the connection. The quick way to test this is to import a registry file that will change this behavior. Copy the data below, save to a text file, rename to rootdomainfix.reg and import into the registry.
Windows Registry Editor Version 5.00 [HKEY_CURRENT_USER\Software\Policies\Microsoft\Office\15.0\Outlook\AutoDiscover] "ExcludeHttpsRootDomain"=dword:00000001