Getting 401 Access denied

[pkamaniMS]

Hi folks. I have been struggling with the following issue all afternoon, which seems like a rookie mistake but I can't figure out. Any help getting past this would be appreciated.
As soon as I try to bind the Inbox folder (var folder = Folder.Bind(exchangeService, WellKnownFolderName.Inbox);), I get an access denied. I am using my inbox, with my creds. I can see that the Autodiscovery URL is resolved as https://outlook.office365.com/EWS/Exchange.asmx. However, anything I try after that results in some exception. Must be doing something wrong. Please help! Here are the things I have tried:

1. UseDefaultCredentials=true instead of specifying my own credentials. (Since I am trying to access my own account).
2. Use NetworkCredentials instead of WebCredentials.
3. Bypass Autodiscovery and specify the URL directly as https://outlook.office365.com/EWS/Exchange.asmx.
4. Use Redmond\pkamani instead of pkamani@microsoft.com as the EWSMailboxAddress account.
5. Explicitly pass in the domain (Redmond) to specify WebCredentials for the ExchangeService account.
6. Change the exchange version from 2010_SP1 to SP2.
7. Get rid of the timeout (since with some of the above changes, it fails to auto-discover).
8. Run with elevated privileges.
9. Use SecureString instead of String as the password param type when creating the creds for the Exchange account.

All these either fail with the access denied error, or fail at auto-discovery itself (timeout). I know the password is correct, since I locked the machine and unlocked it with the same password. The curious thing is that when I directly navigate to https://outlook.office365.com/EWS/Exchange.asmx in the browser, it prompts me for the password multiple times, and eventually shows a blank page. Somehow this leads me to believe that there is a problem with the auto-discovery url. My mailbox is hosted on Office 365.

What bone-head thing am I doing that won't get me past basis EWS auth for my own email account?