We experienced a CRM 2011 Outlook Client that would not connect to office 365. We simply connected via OWA (Web Version of Office 365), and then the fat client connected and configured! It seems the account might have not fully been provisied and logging in via the web client allowed it. We will continue to watch this one, but we wanted to sure just in case you had the same experience.