Solved RDP authentication error has occurred 0x8004005

Few users tried to RDP to the server and received the following error:

Authentication error has occurred 0x8004005

I checked the AD and the account was active. I tried RDP from outside of office and it worked.

Remembered that the last thing done on the network was decommissioning of the old 2003 DC and raising the forest and domain operational levels.

I restarted the 'Kerberos Key Distribution Ccenter' on the DC.

Users could connect via RDP again!