The attached file updates libvirt-bin's upstart job to gracefully shut down VMs when the system shuts down. You can alter the shutdown timeout (SHUTDOWN_TIMEOUT, default: 300s) and list of virsh(1) URIs to use (URIS, default: "qemu:///system") in /etc/default/libvirt-bin.
You'll also need the omit-kvm-vm-pids init script (attachment forthcoming), which copies the KVM pidfiles to /lib/init/rw/sendsigs.omit.d, preventing /etc/init.d/sendsigs from killing KVM VM processes before the updated libvirt-bin upstart job shuts them down.
Finally, this modified upstart job requires the fix for https://bugs.launchpad.net/ubuntu/+source/sysvinit/+bug/639940. Otherwise, the libvirt-bin pre-stop script isn't guaranteed to finish successfully, since sendsigs races the child processes executed during the course of the job script.
With all of these changes, VMs shut down gracefully with the physical host. I would have implemented suspend-on-shutdown (a la the rc script from libvirt 0.8.2), but lucid has an older libvirt that doesn't support 'virsh managedsave'. Shutting down domains gets us *a lot* of the way there, anyway. In fact, I run some largeish KVM hosts, and saving 30-60GB of memory images to disk before shutdown strikes me as less useful than shutting the domains down.
sudo service stop libvirt-bin
sudo cp libvirt-bin.conf /etc/init/
sudo kill -HUP 1
sudo service start libvirt-bin
sudo cp omit-kvm-vm-pids /etc/init.d/
sudo update-rc.d omit-kvm-vm-pids defaults
sudo cp -f sendsigs /etc/init.d/ # get fixed sendsigs from LP#639940