Be sure to attempt to start the service multiple times before assuming failure. Sometimes it helps to wait a few minutes before starting a service. This is especially true if a service depends on another service. Check to make sure that the prerequisite service is fully started.
Restarting the server can do wonders. Sometimes the computer is simply in a state where a restart is required. Programs and subsystems may require cleaning up that only a restart will fix.
If all else fails, run the service as an application. While it is not a perfect solution, it is an acceptable short-term work-around. An advantage of running the service as an application is that the error reporting is usually more detailed. The service should be run as an application only until the service start problem can be solved.