We couldn't connect to the Remote Desktop Gateway because the connection to the remote PC failed. If this keeps happening, contact your network administrator for assistance. Error code: 0x5000004...
I just had this error.
My problem was the end user plugged in a wifi adapter and rebooted the computer. On restart the wifi connected to an open wifi network and the firewall activated as a public network blocking all incoming connections. I disabled the wifi and restarted and the connection then worked fine.
Check the firewall on the local machine to make sure it is allowing incoming connections.