If you've already verified the username/password are correct, then manually specify the EWS Service URL (and unselecting the Autodiscover option) is required.

In most typical situations when using Office 365, the EWS service URL should be set to https://outlook.office365.com/ews/exchange.asmx.  

If that does not work, then you will need to find the EWS service URL that's appropriate for that account. You can google ways to get the service URL and try those approaches. All service URLs should end with "ews/exchange.asmx".

If none of these work, make sure there aren't any firewall or antivirus that might be blocking access to these.