This is the second time this has happened to me, so I'm writing to you, my future self, a quick note so you don't have to relearn this a second time.
If when restarting a DomU, the DomU hangs at "Checking for hardware changes", check on the Dom0 to see if your xenconsoled has died. If so, restart it (ie. /usr/sbin/xenconsoled) and it should immediately fix the hanging DomUs.
This guy has a blog post with same issue, but I don't think he ever figured it out because he took a scorched-earth route to fix the problem. However, it does have a nice screen shot of what the hung DomU looks like.