I was having a lot of trouble getting my Office 365 account setup in Outlook and on mobile until I found these tips. Note that at the time I did not have the settings setup to autodiscover. If you don’t have autodiscover turned on properly then you will definitely need this as help.
Check out the post at http://y0av.wordpress.com/2011/08/31/configure-outlook-for-office-365-manually/. When setting up the account as “Exchange” on mobile try using just “*****.outlook.com” and not adding the “mailbox” part if it does not work with “mailbox” in there.
Basically you just go to “Help > About” and then use the “Hostname” or “Host address” as the Exchange server.
Here is a pdf of the site linked to above in case it ever goes down.