Comment 41 for bug 869635

For anyone for whom the above solutions didn't work, passing "reboot=pci" as described in this page solved the problem for me http://serverfault.com/questions/126571/system-hangs-while-rebooting-on-debian
this appears to be related to acpi issues in the bios; the solutions above did not work for me.
(Disclaimer: this was on linux-mint (no, not the debian version), not ubuntu. However the bug was identical).