That is a tricky issue since you need this service to install things to try to fix the isue with the service that needs to be runing to intall things to try to fix the service that needs to be running to install things to try to fix the service...
Is this recent, anything you can think of that happened right before? Service Pack crashed during setup maybe? Have you tried Safe Mode?