Comment 4 for bug 719833

This sounds a lot like what happened to me when the "fix" for this defect was released: https://bugs.launchpad.net/ubuntu/+source/openssh/+bug/687535

I had to roll back to 5.3p1-3ubuntu4 to be able to restart Xen based Lucid instances and have sshd restart reliably.