If an Enterprise Vault service fails to start, check that the following are running:
Enterprise Vault Directory Service
Either the MSMQ Primary Enterprise Controller or the Message Queuing service