I have the same problem. Installed as service. This is totally weird. First Java 1.4 was installed with Tomcat 6 and it worked. Then Java 1.4 was removed and 1.6 was installed. Tomcat didn't work any more. So additionally installed the 1.4 again. Tomcat still refuses to start.
There are two changes I made:
1. Adjusted the JAVA_HOME environment variable
2. In tomcat6w.exe under JAVA adjusted the path to the jvm.dll in the JVM section.