This may sound trivial, but worth mentioning: You have to build the service (in Visual Studio) - then a DLL will be created in the bin subfolder.
When the service is "deployed" on a server - that bin folder needs to have that DLL file in it - otherwise this error will be thrown...