The IMAP server behind Office 365 seems to often have broken authentication.
I can dig up multiple messages on Microsoft's support forums, but it's 2am on a Sunday night

FWIW - I just added my Office 365 account into Aqua and it worked fine including authentication (server is "outlook.office365.com").
But then, as I recall, the issue is sometimes account specific.
If you know that your password is right, how about contacting Microsoft support?