RDP: error "the remote computer that was reached is not the one you specified"

Issue:

User received this message when trying to remotely connect to a computer.

The connection cannot be completed because the remote computer that was reached is not the one you specified. This could be caused by an outdated entry in the DNS cache. Try using the IP address of the computer instead of the name.

Solution:

Check the clock on both computers and make sure they are both showing the correct time.