I have recently had to deal with the problem of Unified Messaging (aka UM) components not being able to start on a Exchange 2013 multi-role box. I will not dwell explaining what the UM in Exchange 2013 is because it can be found here.
I'd rather share with you what were the symptoms and what was the magic bullet in my case.
First of all both Microsoft Exchange Unified Messaging and Microsoft Exchange Unified Messaging Call router services would fail to start. I had both of these services on my server because it was a multi-role box. Manual attempt to start them would fail with the error 1067: The process terminated unexpectedly.
When checking Event Viewer I have discovered there are errors with ID 4999 and 1038 found in the Application log and 7031 (for each of the service in the System log.
When searching for solution in Google and Bing I was pointed to different articles and forum discussions. Each person posting his/her post was missing this or that component which would prevent successful start of the UM services. In some cases people were missing the right certificate, while in others some files were corrupted, even UMWorkerProcess.exe. Recommendations were different, including re-installing Exchange binaries on the server. Each story would end up either with success or failure.
Checking my server and found out that UCMA 4.0 was missing. Actually, UCMA 4.0 is one of the Exchange 2013 prerequisites which should be installed on a Windows server before the installation of Exchange binaries.
Finding this out made my solution quite successfuly. I have downloaded UCMA 4.0 installation file from here and installed it on my server. Installation is straightforward. All you need is to press Next button couple times and wait till UCMA is installed on the server.
After this I have restarted my server (after all it's running Windows OS) and the services have been restored to functionality. Server Manager dashboard became shiny and both UM and UM Call Router services successfully started and all the dodgy events have stopped being logged to event logs.