How do I use "virsh shutdown" on KVM domains to shut down Ubuntu guests?

Check to see if you have the package acpid installed on each of the guests.

I generally create new virtual machines using VMBuilder with the parameter --addpkg acpid and the only time I've had trouble shutting down Ubuntu guests using virsh was when the guest vm had crashed in some way.