Had a related issue with a different, but similar fix:
I had a Windows service project set to "Any-CPU" using a 64-bit DLL. Same error message. Tried a whole bunch of things, but nothing worked. Finally, I went into project Properties -> Build and noticed that project had "Prefer 32-bit" checked. Unchecked this and no more error.
My guess is that the windows service was expecting a 32-bit DLL, and couldn't find it.