First things first make sure that port 3389 in bound and outbound for tcp and udp are opened on your firewall for this machine. If it is then I would run a tracert from the effected machine like this:
replacing terminalserver for the actual fqdn or ip address of the terminal server. If all that checks out I would reboot the workstation and the terminal server. Post th exact error messages and we will continue to troubleshoot with you.