First up I have to thank http://www.jenovarain.com/2012/09/server-2012-network-location/ for the starting point on this.

A Windows server without a domain was installed but it had both ethernet interfaces listed as Public networks which meant that specific firewall issues existed, including being unable to connect as a remote desktop user. Turning off the Windows software firewall was one option that did allow the RDP connection to be completed, but this was sub-optimal and not persistent after a reboot.

The above-mentioned URL held out the section of the Windows Server Tools that was needed to setup more open access to allow the user to change the network location from Public to Private.

• In “Server Manager” open the “Tools” menu and select “Local Security policy”.
• Select “Network List manager policies” in the console tree.
• Open “All Networks” properties.
• Change “Network location” to “User can change location”
• Now reboot to apply the changes, or at a command prompt use gpupdate /force

But it did not work for me. What I found was that the existing network connection settings were not over-written with the global settings after the reboot.

In the same “Network List manager policies” section, I had to select the specific Network Location and apply the changes there as well. Once that was done, the location could be changed from Public to Private, and my server was accessible with the firewall turned on.