I'm seeing something similar. Running: 1:2013.1+git201305151531~precise-0ubuntu1  from the Ubuntu grizzly testing repo:

I created a network, subnet and router. Linked them all up and then set the router's upstream gateway to be my external network. I then remove it all (clear the gateway, remove the interface, delete the router, subnet and network) and attempt to run quantum-netns-cleanup. The first time I run it I get the following:


quantum-netns-cleanup 
2013-05-17 20:17:23    ERROR [quantum.agent.netns_cleanup_util] Error unable to destroy namespace: qrouter-96ddb034-d577-43e7-89b9-9c39e713c8c9
Traceback (most recent call last):
  File "/usr/lib/python2.7/dist-packages/quantum/agent/netns_cleanup_util.py", line 141, in destroy_namespace
    ip.garbage_collect_namespace()
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 123, in garbage_collect_namespace
    self.netns.delete(self.namespace)
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 402, in delete
    self._as_root('delete', name, use_root_namespace=True)
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 167, in _as_root
    kwargs.get('use_root_namespace', False))
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 47, in _as_root
    namespace)
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 58, in _execute
    root_helper=root_helper)
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/utils.py", line 61, in execute
    raise RuntimeError(m)
RuntimeError: 
Command: ['sudo', 'ip', 'netns', 'delete', 'qrouter-96ddb034-d577-43e7-89b9-9c39e713c8c9']
Exit code: 1
Stdout: ''
Stderr: 'Cannot remove /var/run/netns/qrouter-96ddb034-d577-43e7-89b9-9c39e713c8c9: Device or resource busy\n'
2013-05-17 20:17:23    ERROR [quantum.agent.netns_cleanup_util] Error unable to destroy namespace: qdhcp-a793c185-16f9-483c-b250-09fcac07eb2d
Traceback (most recent call last):
  File "/usr/lib/python2.7/dist-packages/quantum/agent/netns_cleanup_util.py", line 141, in destroy_namespace
    ip.garbage_collect_namespace()
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 123, in garbage_collect_namespace
    self.netns.delete(self.namespace)
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 402, in delete
    self._as_root('delete', name, use_root_namespace=True)
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 167, in _as_root
    kwargs.get('use_root_namespace', False))
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 47, in _as_root
    namespace)
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/ip_lib.py", line 58, in _execute
    root_helper=root_helper)
  File "/usr/lib/python2.7/dist-packages/quantum/agent/linux/utils.py", line 61, in execute
    raise RuntimeError(m)
RuntimeError: 
Command: ['sudo', 'ip', 'netns', 'delete', 'qdhcp-a793c185-16f9-483c-b250-09fcac07eb2d']
Exit code: 1
Stdout: ''
Stderr: 'Cannot remove /var/run/netns/qdhcp-a793c185-16f9-483c-b250-09fcac07eb2d: Device or resource busy\n'

I then attempted to run a command in the router namespace:

ip netns exec qrouter-96ddb034-d577-43e7-89b9-9c39e713c8c9 ip addr show
seting the network namespace failed: Invalid argument

And this behavior is echoed by attempting to run quantum-netns-cleanup again:

quantum-netns-cleanup 
2013-05-17 20:17:51 CRITICAL [quantum] 
Command: ['sudo', 'ip', 'netns', 'exec', 'qrouter-96ddb034-d577-43e7-89b9-9c39e713c8c9', 'ip', '-o', 'link', 'list']
Exit code: 1
Stdout: ''
Stderr: 'seting the network namespace failed: Invalid argument\n'

The DHCP and router namespaces both still exist, but neither can be accessed

ip netns exec qdhcp-a793c185-16f9-483c-b250-09fcac07eb2d ip addr show
seting the network namespace failed: Invalid argument

I checked /run/netns and the files are still there. They are no longer readable, however changing them to +r doesn't allow you to clean them up (it still gives the same error).