Run the following Powershell command on the Coordinator to test sending mail to O365:
$msolcred = get-credential
Send-MailMessage –From <FromAddressEnteredOnTheCoordinator> –To user@yourcompany.com –Subject “Test Email” –Body “Test Text” -SmtpServer smtp.office365.com -Credential $msolcred -UseSsl -Port 587
Enter the credentials specified in the Coordinator SMTP Configuration under the section 'My Server Requires Authentication'. Also test by using -Port 25 instead of -Port 587.
If you get the same error, the issue is most likely with either the credentials you are using or the From address. Try specifying the credentials using an @onmicrosoft.com account.