Нашел ответ сам:
В настройках удаленного рабочего стола перейдите на вкладку «Безопасность» и выберите параметр «Всегда подключаться, даже если аутентификация не удалась».
Еще немного информации:
Ошибка, которую я получил, означает, что клиент удаленного рабочего стола не смог проверить, является ли удаленная машина той машиной, к которой я хотел подключиться.
При подключении к удаленному рабочему столу проверка подлинности сервера подтверждает, что вы подключаетесь к правильному удаленному компьютеру или серверу. Эта мера безопасности помогает предотвратить подключение к другому компьютеру или серверу, к которому вы не собираетесь подключаться.
Это также предотвращает непреднамеренное раскрытие конфиденциальной информации.
http://support.microsoft.com/kb/925876
Таким образом, сообщив клиенту удаленного рабочего стола о подключении, даже если проверка не удалась, проблема была решена.
Видимо, есть некоторые настройки, связанные с этой проблемой, которые можно настроить на удаленной машине, но я не пробовал ни одну из них. http://technet.microsoft.com/en-us/library/cc753945(WS.10).aspx
Я также не проводил никаких исследований, чтобы выяснить, почему клиент не может проверить удаленный сервер.
