One of the most common frustrations I see with people configuring Office 365 is setting up mailboxes. The frustration generally occurs when the autodiscover process fails.
The above video give you a good background on the autodiscover and Outlook set up process as well as the tools you can implement to resolve these frustrating issue. Normally, the solution is quite straight forward but you need to understand the process that Outlook uses when connecting to Office 365. This video will show you that and more.