Encontrei a resposta:
Em Preferências da Área de Trabalho Remota, vá para a guia Segurança e selecione a opção 'Sempre conectar, mesmo se a autenticação falhar'.
Mais algumas informações:
O erro que recebi significa que o cliente de área de trabalho remota não pôde verificar se a máquina remota é a máquina com a qual eu queria me conectar.
In Remote Desktop Connection, server authentication verifies that you are connecting to the correct remote computer or server. This security measure helps prevent you from connecting to a different computer or server than you intend to connect to. This also prevents you from unintentionally exposing confidential information.
http://support.microsoft.com/kb/925876
Então, dizendo ao cliente de desktop remoto para se conectar, mesmo que a verificação falhe, o problema foi resolvido.
Aparentemente, existem algumas configurações relacionadas a esse problema que podem ser ajustadas na máquina remota, mas eu não tentei nenhuma delas. link
Também não fiz nenhuma pesquisa para descobrir por que o cliente não pode verificar o servidor remoto.