Update 1: PPTP Broken? Read our latest article!

Update 2: Even more VPN grief - this time with Windows 8/8.1 Metro and PPTP.  See this article for the solution to "Error 850: The Extensible Authentication Protocol type required..."

For "security reasons" Microsoft somewhat broke the implementation for L2TP/IPSec (and in some cases PPTP) VPNs in Windows Vista/7/2008 R2.  This was due to an architectural change made in these OS versions to disable NAT Traversal functionality for these protocols by default.

This means that while your old XP machine or iPhone will connect, your brand new Windows 7 or 8 system will spin its wheels hopelessly and eventually error out.  Strange, non-obvious and questionable default choice, in our opinion.  You know you are likely experiencing this issue if you try to connect with L2TP and get errors numbers such as 800, 794 or 809.

Thankfully you can bring back the old behaviour with a couple of changes: a registry key and a Hotfix. 

On your Windows Vista, 7 or 8 client machine change or add the following registry item:

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\PolicyAgent\

New DWORD (32-bit) Value:AssumeUDPEncapsulationContextOnSendRule 
Set the value to 2

This allows the client or server to be behind a NAT firewall.

Reboot after making the change, and retry the connection.  If there's still issues, you may have to apply the following Hotfix:

You cannot establish an IPsec tunnel to a computer that is running Windows 7 or Windows Server 2008 R2 through a NAT device

Better still?  Start using SSTP VPNs which will work through virtually any NAT or Firewall device much more consistently, and only requires a cheap or free public SSL certificate.  

This article has more information, and a link to Microsoft's extensive VPN guide.