
Clicking on the error log in the above error message we see the following error:

Problem is, when the health check was performed, the domain was discovered to be in Windows 2003 mode and the password policy was not set to be strict. So what could the issue be? There isn’t much for documentation on the MSOL account creation and the complexity of the account used. I thought maybe we had an issue with the Office 365 tenant, but there is no corresponding account in Office 365 for MSOL.
Next step is to talk to the client. After a few questions, the client remembers that there is indeed a password complexity enforcement product installed. However, it is supposed to exclude the Users directory for the creation of new user accounts. After a bit of working with the product, the client tells me to try again.

Success! So the moral of the story here is to keep digging.
NOTE:If the domain were 2008 + we would have had to examine any granular password policies that were put in place.
More Information
Download Azure AD Connector