Found the answer myself:
In Remote Desktop Preferences, go to Security-tab, and select the option 'Always connect, even if authentication fails'.
Some more info:
The error I got, means that the remote desktop client could not verify that the remote machine is the machine that I wanted to connect to.
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
So by telling the remote desktop client to connect, even though the verification failed, the problem was solved.
Apparently, there are some settings related to this issue that can be tweaked on the remote machine, but I have not tried any of them. http://technet.microsoft.com/en-us/library/cc753945(WS.10).aspx
Nor have I done any research to find out why the client can't verify the remote server.