I am setting up a new Mac and got this annoying error from the Microsoft Remote Desktop client.

Worse, a number of people have complained about this error but there is a lot of useless advice out there, and also the bad advice to disable NLA (Network Level Authentication) on the Windows PC. Don’t do that, it is bad for security.

One of the few helpful threads on the topic is this one which point to this article on the subject of how to enable integrated authentication on Mac and Linux using Kerberos. I followed the advice here and it worked though I’m not sure if the ALL CAPS is necessary for the domain, but I used it and it worked – as long as I entered user@ALLCAPS in the RDP username as well.