This message is displaying inside the Office 365 properties for every user on this account/domain. Multi-Factor Authentication is disabled on the tenant account and I am able to connect with the account using Azure Active Directory Powershell module on the same servers where Adaxes is installed. I also verified that the account the Adaxes services uses can successfully connect as well. I also enabled tracing of requests sent to Office 365, viewed the log and found no errors there.
I tested deleting the tenant and adding it back as well as creating another account with the same level permissions and replacing it as the tenant and still got the same error message. I do have other domains that are working with O365 without issue on the same servers as well.