This is one of the most annoying errors I’ve come across purely as to find the information involved hunting through many layers. For those who want the quick ‘give me something to try please!’ solution, ensure the name of your website instance is 38 characters or less.
The explanation
Let’s create a new website using the Preview Portal:

The name in full is: Test-Virtual-Network-Error-Creating-Website which is 43 characters. Note that we have the Green Tick of Success next to the URL field, this name is perfectly valid (ace!)
So, funny thing, you talk about one naming issue and up pops another - you can also get the Green Tick of Success using spaces in things like the Web Hosting Plan (as I did above):

But that is all LIES!!!! If you do that, you’ll get this error and the website won’t be created

So getting back to the problem at hand, having changed the name of the Web Hosting Plan to a suitable one, the website is created, BOOM!
We want to add to a Virtual Network, but want to create via the website dialog blade, so we navigate (scroll) to the ‘Networking’ section and click on the Virtual Network, errr, button:

We Create new Virtual Network and give a nice succinct name, for example I’m choosing ‘TestVnet’

Easy money, press OK and keep the dream alive.
Oh noes!

We have an error of type: VPNNetworkSetupFailure, with a message of VPNNetworkSetupFailure. That’s cool though, we can click on that and get taken to more det…
ah no.

This is perhaps as informative.
We need info, but where from? Handily the Resource Group holds the key to this issue, so lets boogie on down there

What we’re after in this blade is the events. So, scrolly scrolly, and get to the Monitoring section, let’s click on the Events in the past week ‘button’:

We’ll take the first Failed event and investigate:

At the bottom of the event, in the ‘Properties’ section, we can see the error:

Or in copy/pastable text format:
The provided deployment name 'VPNNetworkSetupForWebsite-Test-Virtual-Network-Error-Creating-Website' has a length of '69' which exceeds the maximum length of '64'.
Azure handily hoofs up 26 characters by prepending ‘VPNNetworkSetupForWebsite-’ before the website name.
If you create the website with 38 characters or less for a name you’ll be just fine.