All created VPNs result in Error 720

I have a few different VPNs I need to connect to. I'm using windows 8 and standard ptpp VPN. Every VPN I have created though results in the same error:

Error 720: A connection to the remote computer could not be established You might need to change the network settings for this connection

The VPN works in Windows 7 and XP. I'm not sure if this has something to do with my new laptop or if its something with Windows 8 itself. Any help would be greatly appreciated and if there is any extra info I can provide please let me know.

Edit:
I've tried with virus scanner turned off and windows firewall turned off as well and I still receive the same error message.

Solution 1:

Got this problem after migrating from Windows 8 to Windows 8.1. It was due to altered miniports which had to be reinstalled.

Here is how I managed to do so:

1. Locate broken miniports [yellow icon]: Device Manager -> View -> Show hidden devices. I had for example 3 bad miniports: WAN Miniport (IP), WAN Miniport (IPv6) and WAN Miniport (Network Monitor).
2. Regedit -> HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Class{4d36e972-e325-11ce-bfc1-08002be10318} -> Export. In the generated .reg file, locate the broken miniports. You will then identify all the subkeys which need to be deleted [for example in my case, subkeys 0039, 0041 and 0042]. Double check that those subkeys has a "DriverDesc" which matches our broken miniports... And delete those subkeys.
3. Go back in Device Manager, and right click on a broken miniport, then "Update Driver Software" -> "Browse my computer" -> "Let me pick driver from a list" -> uncheck "Show compatible hardware" and wait for drivers listing generation... Then pick the first "Microsoft" drivers listed [BlueTooth Personal], and ignore warnings. The broken and undeletable miniport will then become a fake bluetooth card, which you will be able to delete.
4. Repeat point 3 for all broken miniports.
5. And reboot the system. The OS will create again its miniports from scratch.

Solution 2:

It is caused by broken WAN miniports install (You can see yellow exclamation mark next to the WAN Miniport devices in Device manager). I created simple tool which uninstalls all WAN miniports and installs them again, so VPN and Dial-up connections work again. You can find it at Wan miniport repair tool

Solution 3:

It might not be the issue with your VPN but with VPN server. It's possible that your IP address is out of the incoming IP address range defined on the VPN server

• Go to Network and Sharing Center -> Change Adapter Settings
• Right-click Incoming Connections, and then Properties
• Click on the Networking tab and double click on the Internet Protocol Version 4 (TCP/IPv4)
• Click the Specify IP addresses and change/expand an IP range so that include the IPs of your devices, or just change IP addresses on your machines to fit the already defined range

If that was the issue, your VPN should work