Today I was doing migration of an organisation from on-premise to Office365. When running connectivity analyzer, everything was ok and the domain configuration was also configured correctly, but the Outlook 2013 configuration was refusing credentials when trying to setup mailboxes using the AutoDiscovery feature.
I have worked closely with Microsoft on this issue and they are aware of the bug. Talking with an engeener he pointed that the issue comes from SCP lookup is not enabled in outlook 2013 by default. To resolve the issue, you will need to add the following registry keys by hand, or create a new file with the .reg extension and put those lines :
Save the file, and run it.
Now reboot your computer, remove the existing outlook profiles from the control panel.
Create a new profile, and try again with the auto discovery feature.