I am posting this in the hope that it will save someone else the time and effort of figuring this one out:
My current setup is VS2015 against TFS 2013.4
Problem
My old PC setup had VS2013, and I had been using the Microsoft.TeamFoundation.WorkItemTracking.Client namespace to get some Work Item information from TFS.
I recently had to rebuild my PC, and continued development of a program that gets this information.
To my dismay, I kept getting an error:
Unable to load DLL 'Microsoft.WITDataStore32.dll'
You don't need to install the TFS object model/Team Explorer anymore. You can use the NuGet package
Also with the NuGet package, you may run into the same issue that your application cannot find the native DLL.
The text below is copied from https://connect.microsoft.com/VisualStudio/feedback/details/1695433/team-foundation-server-2015-sdk-missing-microsoft-witdatastore64-dll
Microsoft.WITDataStore*.dll is part of the ExtendedClient package, they are native dlls and cannot be referenced in managed project. You will need to manually copy the dll into your bin folder for runtime resolution.
Microsoft.WITDataStore32.dll is in ..\Microsoft.TeamFoundationServer.ExtendedClient.14.83.1\lib\native\x86 Microsoft.WITDataStore64.dll is in ..\Microsoft.TeamFoundationServer.ExtendedClient.14.83.1\lib\native\amd64
(note these paths point to the NuGet package folder)