Hi Derek,

 I just tried your new patches. 
(I couldn't test many times because of the instability of my system.
I will test more when the system gets stable.)
So far, one good news and one bad news.
Good news first.
The previous error is gone. 
Bad news is that the rootfs of LXC instance is not unmounted before rmtree() is called in the nova/virt/libvirt/driver.py file.
I've seen this problem in Essex and in Folsom.
I think this is another bug.
It does not happen always, though.
I suspect there is timing issues between unmount() and rmtree().
This bug eventually leads to "no free nbd device".
If you agree, I can report it as a new bug.

 After terminating instance i-00000005, I still see that its rootfs is mounted to /dev/nbd15:
$ mount
/dev/nbd15 on /usr/local/upstream-Aug-29/instances/instance-00000005/rootfs type ext2 (rw)

 Since it is not unmounted before rmtree() is called, it complains.
Here is the log of nova-compute:
2012-09-04 09:11:46 INFO nova.virt.libvirt.driver [-] [instance: 8e0b9d15-2c4b-40e7-a932-90c8d39d9657] Instance destroyed successfully.
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Attempting to grab semaphore "iptables" for method "_apply"... from (pid=10672) inner /usr/local/nova/nova/utils.py:708
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Got semaphore "iptables" for method "_apply"... from (pid=10672) inner /usr/local/nova/nova/utils.py:712
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Attempting to grab file lock "iptables" for method "_apply"... from (pid=10672) inner /usr/local/nova/nova/utils.py:716
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Got file lock "iptables" for method "_apply"... from (pid=10672) inner /usr/local/nova/nova/utils.py:724
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Running cmd (subprocess): sudo nova-rootwrap /etc/nova/rootwrap.conf iptables-save -c -t filter from (pid=10672) execute /usr/local/nova/nova/utils.py:176
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Result was 0 from (pid=10672) execute /usr/local/nova/nova/utils.py:191
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Running cmd (subprocess): sudo nova-rootwrap /etc/nova/rootwrap.conf iptables-restore -c from (pid=10672) execute /usr/local/nova/nova/utils.py:176
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Result was 0 from (pid=10672) execute /usr/local/nova/nova/utils.py:191
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Running cmd (subprocess): sudo nova-rootwrap /etc/nova/rootwrap.conf iptables-save -c -t nat from (pid=10672) execute /usr/local/nova/nova/utils.py:176
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Result was 0 from (pid=10672) execute /usr/local/nova/nova/utils.py:191
2012-09-04 09:11:46 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Running cmd (subprocess): sudo nova-rootwrap /etc/nova/rootwrap.conf iptables-restore -c from (pid=10672) execute /usr/local/nova/nova/utils.py:176
2012-09-04 09:11:47 DEBUG nova.utils [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Result was 0 from (pid=10672) execute /usr/local/nova/nova/utils.py:191
2012-09-04 09:11:47 DEBUG nova.network.linux_net [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] IPTablesManager.apply completed with success from (pid=10672) _apply /usr/local/nova/nova/network/linux_net.py:369
2012-09-04 09:11:47 INFO nova.virt.libvirt.driver [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] [instance: 8e0b9d15-2c4b-40e7-a932-90c8d39d9657] Deleting instance files /usr/local/nova/instances/instance-00000005
2012-09-04 09:11:47 ERROR nova.virt.libvirt.driver [req-52c4813e-2ae8-4307-af31-158d896fe374 admin admin] Failed to cleanup directory /usr/local/nova/instances/instance-00000005: [Errno 13] Permission denied: '/usr/local/nova/instances/instance-00000005/rootfs/lost+found'

 I can manually unmount it and release /dev/nbd15 to finish the termination process.

 Thanks,
 David