После установки последнего набора обновлений от Microsoft обнаружилось, что virtualbox перестал запускать имеющиеся виртуальные машины. Попытка запуска только что созданной виртуальной машины заканчивалась с той же ошибкой.
Выяснилось, что виновато обновление KB3004394 (December 2014 update for Windows Root Certificate Program in Windows) из разряда рекомендованных. Единственный на сегодня вариант восстановить работу virtualbox — это удалить указанное обновление. Приводятся и иные примеры несовместимости обновления с приложениями.