Visual Studio can actually write logs about its activities if you run it via:
devenv.exe /log
This causes VS to start logging to:
"%AppData%\Microsoft\VisualStudio\[Version]\ActivityLog.xml"
In my case VS 2015 is version 14, so I was looking in:
c:\Users\[account]appdata\Roaming\Microsoft\VisualStudio\14.0
Looking in the logs there was a log entry at ERROR level:
"No InprocServer32 registered for package [Async Query Service Package]"
My guess is the VS 2013 update messed with the dll for that package.
The resolution to this problem was to get VS 2015 to reinitialize itself by running this as an administrator from the Visual Studio command prompt:
devenv.exe /setup
