Thanks. I have found the cause of the problem. For use when connecting to my corporate LAN thru a VPN, on the DNS tab I have specified DNS suffixes to append to unqualified names.
The computer I was trying to RDC to is called htpc. However, there is also a computer called htpc.xyx.com (assuming one of the DNS suffixes I have is xyz.com).
When I try to RDC to htpc, it tries a connection to htpc.xyz.com, which of course fails.
I found this out by doing ping htpc. The response I got was from htpc.xyz.com.