AFAIK there are two different problems here.
As already said by Glenn, replacing the Startup and Shutdown mode by JAva instead of JVM should do the trick for those running tomcat 7.06 +
This can be done by running %TOMCAT_HOME%\bin\tomcat7w.exe and go to the "Startup" and "Shutdown" tabs, then change the "Mode" field from "Jvm" to "Java".
But for those running tomcat 7.04 - you also need to disable the use of the Tomcat.pid file.
This can be done by running %TOMCAT_HOME%\bin\tomcat7w.exe and go to the "Logging" tab, then empty the "PID file" field.
In fact the windows installer automatically configure the use of such a file, but running tomcat as a service fails to delete the file which prevents the service to start again. But it seems that starting the service deletes the file and launching it a second time will succeed.
Hope this helps...