Today i have the problem where a Windows 8 machine, won’t connect to Microsoft VPN server.

The problems was that MSChapV2 was disabled on the client.
Please find this under Security and Allowed these protocols.

The error message I got from both the VPN servers and the client was:

Server:
The following error occurred in the Point to Point Protocol module on port: VPN2-9, UserName: XXXXX\XX. The connection was prevented because of a policy configured on your RAS/VPN server. Specifically, the authentication method used by the server to verify your username and password may not match the authentication method configured in your connection profile. Please contact the Administrator of the RAS server and notify them of this error.

Client:
Error 815: The connection was prevented because of a policy configured on your RAS/VPN server. Specifically, the authentication method used by the server to verify your username and password may not match the authentication method configured in your connection profile. Please contact the Administrator of the RAS server and notify them of this error.

Please see more here: http://jermsmit.com/windows-8-vpn-error-812/