John has kindly pointed out an Ubuntu Bug report where it sounds like someone is suffering the same problem with 2 headless servers.
From the Bug report: "I can only reproduce the problem on servers (with sshd, apache2, mysql, ... no dbus). On desktop installations the restart command works fine. I first saw the problem on lucid but it still occurs on maverick."
Bug report: https://bugs.launchpad.net/ubuntu/+source/udev/+bug/674704
John's post on TKL forums: http://www.turnkeylinux.org/forum/support/20100928/tkl-lucid-core-apt-get-upgrade-freeze-installing-udev-151-121#new