In my experience this error message is always misleading. Typically it's actually a fault of the service exe. With the messagebox displayed, go to a dos prompt and run the EXE. You'll most likely see a stack trace get displayed. If you see a File Not Found Exception then you are probably missing a dependency. Any other error and it's likely to just be a problem with the code.
Typically when integrating a new service into my installs I will set it to start automatically but not author any specific start events. This lets me work the kinks out with the developers before wiring it up fully into the installer.