if you have multiple Runbook Servers for one Orchestrator instance. The Runbooks should switch to another Runbook Servers, if the limit of the Runbooks for the other Server is not reached (how-to-configure-runbook-throttling).
If a Runbook Server Service starts, it needs a connection to the SQL Server with the Orchestrator DB. Is/was this SQL Server running and available during the restart of the Runbook Server?
Anny errors or warnings in the tab "Events" in Runbook Designer? Or any hints in the logs (C:\ProgramData\Microsoft System Center 2012\Orchestrator\RunbookService.exe\Logs)?