All I had to do for an Ubuntu Server guest was install the acpid daemon.
sudo apt-get install acpid
That's all. This was tested on Ubuntu Server 10.10 (Maverick Meerkat) & Ubuntu Server 11.10 (Oneiric Ocelot), but I'm guessing it would work for all other modern flavors of Ubuntu. If you have fixes for other guest OS's, please leave them in the comments.