I solved this by changine the compile options (under project properties) of the service to x86 only.
This prevents Windows 64-bit from attempting to launch the service as a 64-bit process.
(NOTE: I also increased the framework version from 2.0 to 3.5)