A user cannot log in to EWS, possible issue is that the person has a private Microsoft Live account with the same email. Is it possible to specify that the user wants to use their corporate (Office 365) login instead?
When you add the account by going to Menu > Accounts > Add Account, and entering the email address in the automatic setup, after a few questions you will be passed to your browser to authenticate the credentials. In the browser window, you will be able to choose which one to use.
Thanks for the suggestion. I actually got maybe a bit lucky. The client got stuck on something at some point, so I killed it in the process list and then after restart it asked me about the account type as well. I wanted to avoid removing and adding the account as it is huge for synchronization.