I found that when I tried to install the
virtualbox package through aptitude, I got this error:
First Installation: checking all kernels... Building only for 3.0.0-12-generic-pae Module build for the currently running kernel was skipped since the kernel source for this kernel does not seem to be installed.
Closer inspection showed that although I had the generic headers for this kernel, I didn't have the pae version (I only upgraded this machine a couple of days ago which doesn't help). To add the headers I needed, I simply did:
sudo aptitude install linux-headers-3.0.0-12-generic-pae
I was then able to install virtualbox successfully, and create a shiny new Xubuntu VM for my course attendees to use later in the month.