VPN

We are connected through Cisco 1800’s. When I remote in to our Terminal Serices Server I can’t connect. “The client could not connect to the remote comptuer…..etc…) But when I try to connect to our main data server it works just fine. I have about 50 clients connecting to the terminal server with no problem, and I also have additional unused licenses. I tried deleting the Microsoft License key but did not work. Does anyone have any other suggestions to try?