I saw this morning that Sun released VirtualBox 2.0 (it was released last Thursday, but had missed that). The big update (at least to me) is that it now supports 64-bit guests (on 64-bit hosts). I added the deb packages for my Ubuntu box and installed the virtualbox-2.0. The package installed properly, but the icon I had been using to launch the program went away and launching from the terminal also disappered.
The fix was pretty quick, but took a couple of minutes to locate. On top of installing the new package, you also need to run the vboxdrv setup to recompile the kernel module.
sudo /etc/init.d/vboxdrv setup
After you run this, everything runs wonderfly again :)