I had the same problem and solved it by running the following command:
sudo /Library/StartupItems/VirtualBox/VirtualBox restart
In later versions, the command is
sudo /Library/Application\ Support/VirtualBox/LaunchDaemons/VirtualBoxStartup.sh restart
Make sure you've unblocked VirtualBox's kernel extensions in System Preferences->Security and Privacy->General (You'll get a popup when you install VirtualBox).