I downloaded this:
http://docs.unity3d.com/uploads/Main/SimplestPluginExample-4.0.zip
When I open the project “Unity Project Plugin” in Unity 5.2.2 and run it I always get “DllNotFoundException: Assets/Plugins/ASimplePlugin.dll”.
But the thing is that there is Assets/Plugins/ASimplePlugin.dll. The same problem on Linux. I must be doing something wrong, but what? 
I tested on 64-bit Windows 8.1 and 64-bit Ubuntu 14.04.
Edit: This seems to a 32-bit vs 64-bit issue.
Make sure that the plugin importer settings are setup correctly and the dll is working on your platform.
If i’m not wrong the example plugins are from a time that unitys 64 bit version was non existent and so they are probably all only X86 (32bit) compatible. The normal unity5 version is 64 bit and will not work with 32 bit dlls.
You need to get it compiled for 64 or use the 32bit editor (what i would not recommend).
Edit: missed your edit , good that you found the problem.