I'm facing a similar problem. I have a server and three clients connected to the same network through the usual cable modem provided by comcast. I have a static IP address assigned to the connection but am not able to connect to the server remotely. I have Remote connection enabled on the server and also have listed users with permissions to log on to the server! Any help is greatly appreciated! NR LG

You likely have the firewall on the server enabled. In order to VPN in, you would have to open the appropriate port on the firewall to allow the traffic through.

Well, you do know that the built in Remote Desktop feature is by default in Administration Mode and only allows Two concurrent connections. Also, there is a understanding that by default the connting users are in the Domain Administrators Group (Since this is in Administration mode). What this means is by default users that login have 100% full control of the server. Such as Installing/Uninstalling apps and components and shuting down or rebooting the server. Yes you can create a user or group and give them access while reducing those types of access, but in Administrator Mode it's not a best pratice. What you need to support multiple users (in Non Administrator mode) is Application mode support. In either case if the server is being proxed or firewalled in any way, port 3389 from the Internet needs to be allowed to the Server. So, that implies a NAT and/or port redirection depending on your setup. Hope that helps ya.

I would check to see if you have proxy or firewall in placed? If so, disable it or open a port like SJafiu told you. Right click on server "my computer" in the "remote" tab make sure to check "allow remote connection" like you've said you've did. from clients, go to "run" and type "mstsc" which is a microsoft remote connection and enter your server IP address and login with "Administrator" and your "password" It should be just fine!