"Cannot connect to the virtual machine." for new Hyper-V Virtual Machine

I found my specific issue. The VPN software that I used was preventing me connecting to the virtual machines. I uninstalled the VPN software and it worked fine.

The VPN software was Astrill, which I use to test CDNs and how websites look when connecting from various places around the world. This may no longer be an issue with the latest version.

I'm now running the VPN from within a virtual machine, which works fine and doesn't interfere with the Windows 8 network stack.

I fixed it by allowing VMMS.EXE (Located in C:\Windows\System32) through my firewall (Sophos) and allowing IPV6 traffic.