We were stuck with this when trying to connect to an RDP host that was behind on its updates and had its NLA requirement enabled. Since we had no way to remotely connect to the host to install updates or disable NLA, we were able to override this requirement on the remote machine by modifying the registry on the remote machine:

REG ADD HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System\CredSSP\Parameters /v AllowEncryptionOracle /t REG_DWORD /d 2

This allowed the remote connection to succeed. This can be reversed after resolving the host problem with this on the remote machine:

REG ADD HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System\CredSSP\Parameters /v AllowEncryptionOracle /t REG_DWORD /d 0