This is post is now quite old and the the information it contains may be out of date or innacurate.
If you are using Ubuntu (or probably other versions of linux as well) and the OSE version of Virtualbox, then after upgrading you might find that your virtual machine images no longer run.
The solution is really simple.
Uninstall VirtualBox OSE
Go to the Official VirtualBox Downloads Page and download the correct version for you platform. You should find that it runs your images fine and wont be susceptible to this upgrade problem in future.
another problem solved :)