I had the same problem!
Found out, that the service.bat didn't configure the service the right way. If you enable the logging from your service starter:

Then you'll see in your loggs something like:
[2014-02-19 16:40:35] [error] ( javajni.c:863 ) [ 2636] FindClass org/apache/catalina/startup/Bootstrap failed
[2014-02-19 16:40:35] [debug] ( javajni.c:964 ) [ 2636] Java Worker thread finished org/apache/catalina/startup/Bootstrap:main with status=3
[2014-02-19 16:40:35] [error] ( prunsrv.c:1183) [ 5000] Failed to start Java
[2014-02-19 16:40:35] [error] ( prunsrv.c:1536) [ 5000] ServiceStart returned 4
You'll notice that there is some classpath problem with the starter. In fact that's the problem! Your service.bat didn't configure the service the right way:

Note: You can also choose "Use default" above "Java Virtual Machine" to use whatever JVM is defined in JAVA_HOME
You'll need to set the classpath correctly:
c:\webclient\apache-tomcat\bin\tomcat-juli.jar;c:\webclient\apache-tomcat\bin\tomcat-juli.jar;c:\webclient\apache-tomcat\bin\bootstrap.jar
In my case i "installed" tomcat at: c:\webclient\apache-tomcat replace that part with yours. In my case not even the Java VM was set.. I'm not shure whether this is a problem with the current versions of tomcat (and it's service.bat), or with some sort of permission problem on the windows server itself..