随分前から話題になっていましたが、まだ回避できていない方がいるようなので私が現在取っている回避策を紹介しておきます。
Windows Updateによって規定のセキュリティレベルが高まり、その影響でRDP接続できなくなる…という事象ですね。

とりあえず上記のようにローカルコンピューターポリシーをいじってしまえばUpdateされていないWindows Serverに対してもRDPが可能となります。
もちろん「脆弱」でありずっとこのまま運用してよいわけではありませんので、きちんとサーバーもクライアントもUpdateをして回ってもらえればと思います。
なお、私自身は出会っていないので詳細なエラーメッセージですとかパターンがわかっていませんが下記のようなエラーメッセージが出るようです。
認証エラーが発生しました。 要求された関数はサポートされていません
原因は CredSSP 暗号化オラクルの修復である可能性があります。