Comment 6 for bug 1012595

Just to record it for posterity:

cloud-init in Oneiric (only! (see bug 890501 and bug 871966 for context)) would add an entry to /etc/hosts, which is why the problem didn't exist there. In Precise, there's no entry for $fqdn in /etc/hosts, so we rely on DNS to look that up. However, the DNS lookup coincided with the reconfiguration of the network that happens when the first instance is run on a nova-compute node.

The original analysis was thus wrong. Seeing things like:

libvir: QEMU error : Domain not found: no domain with matching name 'instance-00000001'

is perfectly normal and expected behaviour prior to the first launch of an instance.