Remote desktop connection error after updating Windows 2018/05/08 - CredSSP updates for CVE-2018-0886

(Posted an answer on behalf of the question author).

As in some answers, the best solution for this error is to update both server and clients to version >= the 2018-05-08 update from Microsoft.

If you cannot update both of them (i.e. you can only update client or server) then you could apply one of the workarounds from the answers below, and change the configuration back ASAP so that you minimise the duration of the vulnerability introduced by the workaround.

Alternate method to gpedit using cmd:

reg add "HKLM\Software\Microsoft\Windows\CurrentVersion\Policies\System\CredSSP\Parameters" /f /v AllowEncryptionOracle /t REG_DWORD /d 2