At Grub, choose the super-user mode
(usually the second option on the list) and then
once you have a terminal apt-get install the
VirtualBox package again to see if by
installing it back will get all of the dependencies
that were removed. I have always thought that
"complete removal" must be taken with care.