This can be caused by Team Coherence Server being installed on a Subst'd drive. Because there is no way for Team Coherence Server Configuration tool to determine what the real path is, the service is configured to run using the substituted path.

At boot time, if the Service Manager cannot locate the service binary, the service will not be started. In other words, the Server should be installed on a drive that is available at boot time on the machine in question.