Remote Desktop connection: "the identity of the remote computer cannot be verified"

Problem:
Trying to establish a remote desktop connection from a Win2008 Server (SP2) to other Win2008 Server (SP2) fails with the following error message "The connection cannot continue because the identity of the remote computer cannot be verified".

Solution:
This might be caused by incorrect time on one of the Win 2008 servers. Correct the time or activate automatically time synchronization for each server.

An additional Workaround:
If the described time correction has not solved the problem, then you may try to use the IP address instead of the host name to establish the connection.