В общем была такая же беда, обновил систему до Ubuntu 12.04 LTS и virtualbox перестал заводится, сначала удалил его переставил новый, но проблема не исчезла, после этого даже новый виртуальный диск не получалось создать. При выборе типа файла выдавал ошибку...
Испробовал всеразличные способы, в итоге снес все полностью и папки и все виртуальники и любое упоминание о прошлых виртуальных системах поставил synaptic установил по новой Oracle VM Virtualbox, но ошибка все равно осталась...
Может быть решение и не правильное, но сделал следующее при загрузке ubuntu, есть экран с выбором Обычная загрузка, загрузка консоли и Memory Test... Запустил этот мемори тест, подождал пока все проверит. Перезагрузился. И при загрузке Ubuntu вижу знакомую ошибку, но она исправлена...
Собственно поставил по новой гостевую систему и никаких проблем не возникло...До этого не подключался интернет в гостевой, теперь сразу автоматически, настроился и интернет... Я новичек во всем этом деле, но собственно, у меня проблема решилась таким путем, может и не весьма правильным...