I encountered this error while working on a SSL (SSTP) VPN setup. The distinctive characteristic was that we defined the VPN host in the computer's hosts file, although the same error could be encountered by an improperly configured DNS entry.
One potential source of this error is simple name resolution. Make sure you can ping the host the way it is typed into the Windows VPN Connection. If you cannot resolve the host name to ping it, then you will not be able to resolve it to connect over VPN. Of course, the error message does not say that plainly at all. In fact, the error message does not necessary communicate that it relates to host or IP data at all.
If you dig and dig, you can track the code back to WSANO_DATA, which essentially explains that the host name lookup failed.