GRUB can't configure on upgraded Ubuntu OpenVZ VPS

I upgraded an OpenVZ VPS from an older Ubuntu release to 12.04LTS using the do-release-upgrade command. Ever since, all of my apt-get runs look something like this:

$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
3 not fully installed or removed.
After this operation, 0 B of additional disk space will be used.
Do you want to continue [Y/n]? Y
Setting up linux-image-3.2.0-35-generic (3.2.0-35.55) ...
Running depmod.
update-initramfs: deferring update (hook will be called later)
Examining /etc/kernel/postinst.d.
run-parts: executing /etc/kernel/postinst.d/dkms 3.2.0-35-generic /boot/vmlinuz-3.2.0-35-generic
run-parts: executing /etc/kernel/postinst.d/initramfs-tools 3.2.0-35-generic /boot/vmlinuz-3.2.0-35-generic
update-initramfs: Generating /boot/initrd.img-3.2.0-35-generic
run-parts: executing /etc/kernel/postinst.d/zz-update-grub 3.2.0-35-generic /boot/vmlinuz-3.2.0-35-generic
/usr/sbin/grub-probe: error: cannot find a device for / (is /dev mounted?).
run-parts: /etc/kernel/postinst.d/zz-update-grub exited with return code 1
Failed to process /etc/kernel/postinst.d at /var/lib/dpkg/info/linux-image-3.2.0-35-generic.postinst line 1010.
dpkg: error processing linux-image-3.2.0-35-generic (--configure):
 subprocess installed post-installation script returned error exit status 2
dpkg: dependency problems prevent configuration of linux-image-generic:
 linux-image-generic depends on linux-image-3.2.0-35-generic; however:
  Package linux-image-3.2.0-35-generic is not configured yet.
dpkg: error processing linux-image-generic (--configure):
 dependency problems - leaving unconfigured
dpkg: dependency problems prevent configuration of linux-image:
 linux-image depends on linux-image-generic (= 3.2.0.35.40); however:
  Package linux-image-generic is not configured yet.
dpkg: error processing linux-image (--configure):
 dependency problems - leaving unconfigured
No apport report written because the error message indicates its a followup error from a previous failure.
                      No apport report written because the error message indicates its a followup error from a previous failure.
                                                Errors were encountered while processing:
 linux-image-3.2.0-35-generic
 linux-image-generic
 linux-image
E: Sub-process /usr/bin/dpkg returned an error code (1)

I am reasonably sure that something about the OpenVZ environment is causing this problem, likely the simfs / and the lack of any disks (hd_) in /dev. But despite spending the last few hours reading all I can find on the /usr/sbin/grub-probe: error: cannot find a device for / (is /dev mounted?). error, I still have this problem.

Worse comes to worse, I can restore from a backup that should be clean. But I would rather not do that, as it would mean some tricky BOINC-related footwork to resync with attached projects.