I have run into this a few times so pasting it here for reference. The fix is to set the below registry key from 1 to 2 on the machine that is initiating the remote desktop (source machine). A reboot is not required.
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Policies\System\CredSSP\Parameters]
"AllowEncryptionOracle"=dword:00000002
