SOLVED: Remote Computer Requires Network Level Authentication

We recently had a client with several Windows Server presenting this error message when admins were attempting to RDP to them:

REMOTE DESKTOP CONNECTION
The remote computer that you are trying to connect to requires Network Level
Authentication (NLA), but your Windows domain controller cannot be contacted to perform
NLA. If you are an administrator on the remote computer, you can disable NLA by using the
options on the Remote tab of the System Properties dialog box.

After several work-around attempts failed, we disabled NLA on the remote computers using this simple script:

(Get-WmiObject -class "Win32_TSGeneralSetting" -Namespace root\cimv2\terminalservices -ComputerName "Target-Machine-Name" -Filter "TerminalName='RDP-tcp'").SetUserAuthenticationRequired(0)

Just replace TARGET-MACHINE-NAME with the actual host name and make sure you run this in a PowerShell or Windows Terminal session that is running as an administrator.