Domain Rewrite: Trying to set up demand re-write and running into a problem - error: "PowerShell not available for BinaryTreePowerShellUser" (4369208)

Domain Rewrite: Trying to set up demand re-write and running into a problem - error: "PowerShell not available for BinaryTreePowerShellUser"

Trying to set up demand re-write and running into a problem. We see the following error message, what could cause this?
error: "PowerShell not available for BinaryTreePowerShellUser"

One or more of the following could cause this error:

Multi-factor Authentication is enabled
The account is included in a Conditional Access policy enabled for the Powershell account.
Account does  global admin privilege
Is not licensed or is not a member of the Exchange Administrators group and does have an Exchange Online license installed.
Remote powershell not enabled for PS binarytree powershell account
One or more of the below setting are set to not allowed.
Remote PowerShell
Basic authentication


 

Disable Multi-factor Authentication
Exclude the account from Conditional Access Policy

Is licensed and is a member of the Exchange Administrators group and does have an Exchange Online license installed.
Remote powershell enabled for PS binarytree powershell account

Confirm  remote PowerShell and basic authentication are allowed
Account has global admin privilege