The introduction of Active Directory Authentication Library (ADAL) support in Office 2013 and Office 265 ProPlus is great news. The Office suite of applications is now able to take advantage of advanced authentication options like federated SSO and MFA. Using ADAL with Office is referred to using Office with modern authentication. Modern authentication was recently made available to everyone and all you need to do to start using it is add three registry keys. You can find all the information you need here:

http://blogs.office.com/2015/03/23/office-2013-modern-authentication-public-preview-announced/

I recently ran into a problem with using ADAL in Office, which I think is a bug. When you try to connect to a new mailbox in Outlook using Autodiscover, and who doesn’t, Outlook is unable to successfully connect to the mailbox. From my testing, this problem is present in version 15.0.4693.1002 of Office 2013/365 ProPlus (a.k.a. March 2015 Update), which is the first version to include ADAL support.

You can look at the change log for Office here: https://support2.microsoft.com/gp/office-2013-365-update

Check your Office version by going to FileAccount and looking at Product Information:

The problem manifests itself when using the Account Setup Wizard.You enter your name, email address and password. Outlook queries Autodiscover DNS records for your domain. When your settings have been discovered you are asked to authenticate against the service. This authentication does not used ADAL in my experience, but displays an old fashioned authentication prompt. However, because of the bug, you will never get this far. Instead the wizard will inform you that it cannot find your settings.

To fix this, simply update to the latest version of Office. The most recent update, at the time of this writing, is version 15.0.4711.1003 (a.k.a. April 2015 update).

None of the fixes in this update specifically addresses this problem, as described in this post, but there is some mention about not being able to add a new account if your are using ADAL in Office and the account uses basic authentication in this KB article:

https://support.microsoft.com/en-us/kb/2965218

• When you enter incorrect credentials for an account that makes some mailbox connections use Active Directory Authentication Library (ADAL) authentication and some connections use basic authentication, you are not prompted to enter credentials again, and Outlook cannot connect to mailboxes by using basic authentication.
• When you enable the Active Directory Authentication Library (ADAL)-based authentication for Outlook 2013, you may be unable to add Office 365 accounts that use basic authentication. If you have enabled the ADAL-based authentication for Outlook 2013 that has an Office 365 account configured and the account uses basic authentication, you cannot connect to the account.

Anyway; updating resolves the problem.