First I stumbled upon this article on Microsoft's website by changing my google search to fix the problem. I started searching google with the following:
"open with" context menu missing
That brought up the results with the first being a microsoft link:
"Open With" Command Missing from the Context Menu
Now the article didnt tell me exactly how to fix it but it gave me an idea.
It said to examine the following reg key:
HKEY_CLASSES_ROOT\Unknown\shell\openas\command
And it said to look at the following default value:
C:\%windir%\rundll32.exe shell32.dll,OpenAs_RunDLL %1
After looking at this I noticed the value was different but then I noticed the article said this applies to Windows 95 and 98.
I then looked at the same key on my laptop which is also running Vista Ultimate 32bit and I noticed there were subfolders on my laptop that my desktop did not have.
It should look like the following:
HKEY_CLASSES_ROOT\Unknown
\DefaultIcon
\+shell
\+openas
\command
\+opendlg
\command
My desktop only had the DefaultIcon folder.
Well I just copied the key from my laptop and voila...it worked.