Since the update late 2013 to our Office 365 tenency we've had problems with users loading Outlook 2010 and connecting to Office 365. We use SSO with AD integration. Users will often load outlook only to wait 30 seconds before the 'Retry or Cancel' pop up box appears, caching is disabled. The strangest thing is this doesn't always happen and when it does 90% of the time Outlook will load within 5 seconds of clicking retry. Once users are logged in closing outlook and reloading generally seems more reliable but even then its not unheard of for the same problem to occur. Creating new email profiles didn't help, they create fine autodiscover works fine and then once they try to connect with the new profile the same as above can occur. It seems to randomly affect near all users and all locations.

The following addresses have been except:
mail.ourdomain.com; office15client.microsoft.com; office.microsoft.com; ;office365.com outlook.office365.com

Wire shark also shows nothing being denied or any errors and outlook webapp works perfectly for all users straight away. The same occurs with Office 2013. Has anyone here experienced similar or any suggestions on resolving it?