If your virtual machine does not shut down when asked by the hypervisor, install the package acpi-support.

Works at least with KVM, but I see no reason why it would not work as well in other virtualization platforms, if they just send the ACPI shutdown signal to VM.

Thanks:

• Virtualbox ACPI Shutdown on Ubuntu Lucid Lynx « The Redscreen Blog.