Hello again -
I posted this question a while back and abandoned it as I was pulled in a different direction 
Alas, I have returned and wanted to post my finding about it in the hope that I can save some people hours of banging their heads against their desk!
The Scenario
Simply put, I want to create a User Story in a project within Visual Studio Online. I want a user to fill out a form and then pass that information over into VSO. This is to be used for a web support team as a request form and queue for updates/changes to internal websites.
The Setup
Before we dive in, as always, lets take a minute to understand what we want to do and what we need to do.
- Build a form to collect data
- Build a workflow to pass data
Simple, right?
I do recommend that you take a look at the following sites as reference if you are unfamiliar with Visual Sudio APIs:
Getting Started: Auth Overview
Creating Personal Access Tokens
I am going to assume you have a basic understanding of Nintex Workflow 2010, and more specifically the Web Request Action, but if not, check out Nintex Help - Web Request.
The Visual Studio Parts
In order for this to all work, we need to make sure that the web service call has the proper authorization to create the work items in our project. To do this, we will create a Personal Access Token. Simple navigate to your Visual Studio Online environment and from the homepage open your profile and click on "Security".
Next you will want to Add a Personal Access Token. This will generate a unique key that you can set to expire as well as what scope it pertains to:
Once you have the key (be sure to copy and paste it somewhere because you cannot view it again after it is gone) you will need to encrypt your token in Base64 so that you can use it in an HTTP Header (which is what we will do).
When encoding your token, do not forget your login! So for example, it will look like this:
{yourVisualStudioUserName}:{YourPersonalAccessToken}
jmchargue@duqlight.com:yourpersonalaccesstoekngoeshere
When you encrypt it, it turns out like this:
am1jaGFyZ3VlQGR1cWxpZ2h0LmNvbTp5b3VycGVyc29uYWxhY2Nlc3N0b2VrbmdvZXNoZXJl
Once you have that setup we can move into the Nintex side of things 
The Nintex Parts
I am not going to go over the form because I want to focus on the "how we connect Nintex Workflow to VSO".
You can make the form anyway you want with any data points and controls you see fit. Here is my form (no extras added):
I know its is not pretty, but we are going for functional! The workflow is where the magic happens so lets dive into that.
At the core, we want to leverage a Web Request action. I use some other actions to help set variables (query user profiles, etc), but the focus is on the Web Request.
You will want to use a PATCH and point your web request action to your project within Visual Studio:
PATCH https://{instance}/DefaultCollection/{project}/_apis/wit/workitems/${workItemTypeName}?api-version={version}
Your headers will be as follows:
Content-Type: application/json-patch+json
Authorization: Basic {YOUR Base64 ENCRYPTED USERNAME:TOKEN}
Lastly, you will want to add your request body. For this example, I am creating a User Story and this is the body:
[ { "op": "add", "path": "/fields/System.Title", "value": "{ItemProperty:Title}" }, { "op": "add", "path": "/fields/System.Description", "value": "{WorkflowVariable:var_FN} {WorkflowVariable:var_LN} <div>{WorkflowVariable:var_Email} </div><div>{WorkflowVariable:var_PhoneNum} </div><div>Description: </div><div>{ItemProperty:Description}</div>" }, { "op": "add", "path": "/fields/System.AssignedTo", "value": "{WorkflowVariable:var_assignedTo}" }]
Web Request Action Sample:
Run Now:
I recommend that the first time you simply try to create an item with a title so you do not get hung up on all the other properties. I have had some success with doing a "Run Now". I would recommend using it, but I use Fiddler or Postman to remove any issues that SharePoint may present. More on that later.
Results
Now that we have everything in place, let's create one and see it go through!
Form (I had someone else fill it out to test permissions at the same time ):
And here it is in Visual Studio:
It works (yay)!
Final Thoughts
I recommend doing this in Postman or Fiddler first so that you can understand how the web service work and hammer out the syntax. I spent countless hours attempting to connect to realize I left off the "username@domain" from my access token... yea... it happens.
Also, using Postman or Fiddler allows you to operate outside of SharePoint. We ran into issues trying to get the call to go out of our network... more wasted time, but figured it out in the end. Knowing that it works in one place can help determine issues and causes.
Next I want to recreate this in Office 365. I would like to use Nintex Workflow Cloud, but did not see a Web Request action yet.
Hope this helps, and as always, until next time!
