Решение:
1. Запустить службы от пользователя, под которым устанавливался MS Project Server
2. Добавить в файл c:\WINDOWS\system32\drivers\etc\hosts строчку «127.0.0.1 crl.microsoft.com»
или разрешите выход в интернет для учетной записи, которая используется для запуска службы, с данного сервера на период регистрации службы на crl.microsoft.com (минута максимум).