RDP Client Cannot Connect

When ever I try to connecet to the Remote Desktop Connection, I always get an error message that says: “The client could not establish a connection to the remote computer.” Then it tells me a couple of things I coulds try to fix it. Of course, I cannot get it to work still. I was wondering if anyone has encountered this problem before, and if so, how to fix it. So far the only way we have been able to fix it is to format the machine from scratch, which is definitly not the best way to do it. Thanks