Встретил несколько решений на просторах интернета, одним из них было предложено подключить CredSSP - это мне не помогло. Отключение проверки подлинности на стороне сервера терминалов тоже ничего не дало.
Поэтому пришлось сориентироваться и придумать решение.
Сперва я попробовал установить альтернативные программы вроде mRemoteNG и RemoteDesktop Connection Manager. К моему удивлению они прекрасно работали и без всяких ошибок. Отсюда у меня возникла мысль обновить штатный клиент remote desktop connections. Был установлен версии 6. На сайте Microsoft предлагается обновить до версии 7 - ссылка для скачивания
После обновления я получил уже другую ошибку - Произошла ошибка проверки подлинности. Затребованный пакет безопасности не существует.
Я попробовал подключиться к локальному компьютеру и никаких ошибок не увидел. Поэтому решил, что однозначно проблему надо решать на стороне сервера.
Проблема решилась сменой Уровня безопасности на значение "Уровень Безопасности RDP".