Exchange 2016 Install - Hybrid Deployment Check - The username or password is invalid

Hi,

We have exchange 2010 with Exchange Online in hybrid mode.  We are trying to install Exchange 2016 CU18 on a new server, on the setup we are getting prompted to enter a user name and password to connect to Office365:

Problem is it keeps coming back invalid username or password.  The account is right and permissions fine.  Network have confirm nothing is getting blocked, local firewall is off. 

This is from the ExchangeSetup.log:

[09/25/2020 10:37:46.0346] [0] Finished loading screen HybridConfigurationStatusPage.
[09/25/2020 10:37:47.0867] [0] Finished loading screen HybridConfigurationCredentialPage.
[09/25/2020 10:45:39.0576] [0] Starting hybrid configuration checks...
[09/25/2020 10:45:39.0576] [0] Running the Office 365 tenant hybrid test.
[09/25/2020 10:45:39.0576] [0] The hybrid detection engine will try to connect to Office 365 using the provided tenant credentials to run the Get-OrganizationConfig cmdlet.
[09/25/2020 10:45:39.0576] [0] Opening runspace to https://ps.outlook.com/powershell-liveid?serializationLevel=Full.
[09/25/2020 10:45:39.0748] [0] Session=Tenant Total Cmdlet Time=0s
[09/25/2020 10:45:39.0748] [0] Microsoft.Exchange.Management.Deployment.HybridConfigurationDetection.HybridConfigurationDetectionException: The username or password is invalid. ---> System.Management.Automation.Remoting.PSRemotingTransportException: Connecting to remote server ps.outlook.com failed with the following error message :  For more information, see the about_Remote_Troubleshooting Help topic.
   at System.Management.Automation.Runspaces.AsyncResult.EndInvoke()
   at System.Management.Automation.Runspaces.Internal.RunspacePoolInternal.EndOpen(IAsyncResult asyncResult)
   at System.Management.Automation.RemoteRunspace.Open()
   at Microsoft.Exchange.Management.Deployment.HybridConfigurationDetection.RemotePowershellSession.Connect(PSCredential credentials, CultureInfo sessionUiCulture)
   at Microsoft.Exchange.Management.Deployment.HybridConfigurationDetection.HybridConfigurationDetection.RunTenantHybridTest(PSCredential psCredential, String organizationConfigHash)
   --- End of inner exception stack trace ---
   at Microsoft.Exchange.Management.Deployment.HybridConfigurationDetection.HybridConfigurationDetection.RunTenantHybridTest(PSCredential psCredential, String organizationConfigHash)
   at Microsoft.Exchange.Setup.GUI.HybridConfigurationStatusPage.StartHybridTest()
[09/25/2020 10:45:39.0779] [0] Finished loading screen HybridConfigurationStatusPage.

Anyone got any ideas on what to do next?