I had this problem, it took about a day to fix. For me the problem was that my code skipped the "main content" and effectively ran a couple of lines then finished. And this caused the error for me. It is a C# console application which installs a Windows Service, as soon as it tried to run it with the ServiceController (sc.Run() ) then it would give this error for me.
After I fixed the code to go to the main content, it would run the intended code:
ServiceBase.Run(new ServiceHost());
Then it stopped showing up.
As lots of people have already said, the error could be anything, and the solutions people provide may or may not solve it. If they don't solve it (like the Release instead of Debug, adding generatePublisherEvidence=false into your config, etc), then chances are that the problem is with your own code.
Try and get your code to run without using sc.Run() (i.e. make the code run that sc.Run() would have executed).