Well, I think I've tracked it down:

The VM can't be started and virsh shows the above mentioned error when the qcow2 disk source file is located in /etc (at least when in /etc/libvirt/qemu or /etc/network). So the following snipplet in the XML file triggers the error:
    <disk type='file' device='disk'>
      <source file='/etc/libvirt/qemu/infra01/disk0.qcow2'/>
      <target dev='hda' bus='ide'/>
    </disk>

While something like
   <disk type='file' device='disk'>
      <source file='/srv/cyt.ch/kvm/infra01/disk0.qcow2'/>
      <target dev='hda' bus='ide'/>
    </disk>
works like a charm.

Well, it's absolutely stupid to create disk files in /etc, I know. Was triggered by simply running ubuntu-vm-builder from those directories while not being fully awake...

Well, in the end I think it's a sysadmins decision where to put those disk files. While /etc is really stupid, there might be some other places "silently forbidden" by apparmor. I think while some more bugs like this will be filed if there's no better error message... For this reason, I'm leaving this bug open, even though it could be considered invalid...

Well kern.log is quite quiet:
Mar  2 14:53:54 leo01 kernel: [84139.330434] type=1505 audit(1267538034.463:52): operation="profile_remove" info="failed: profile does not exist" pid=11213 name=libvirt-009c6a05-d841-2b80-51ac-fc940f0000f4 namespace=default

syslog is more verbose:
Mar  2 14:53:54 leo01 libvirtd: 14:53:54.226: error : virSecurityReportError:108 : error calling aa_change_profile()
Mar  2 14:53:54 leo01 libvirtd: 14:53:54.226: error : qemudSecurityHook:1790 : internal error Failed to set security label
Mar  2 14:53:54 leo01 libvirtd: 14:53:54.227: error : virExecDaemonize:678 : internal error Intermediate daemon process exited with status 1.
Mar  2 14:53:54 leo01 kernel: [84139.085901] device vnet2 entered promiscuous mode
Mar  2 14:53:54 leo01 kernel: [84139.086434] br_dmz: port 2(vnet2) entering learning state
Mar  2 14:53:54 leo01 kernel: [84139.114878] br_dmz: port 2(vnet2) entering disabled state
Mar  2 14:53:54 leo01 kernel: [84139.154409] device vnet2 left promiscuous mode
Mar  2 14:53:54 leo01 kernel: [84139.154413] br_dmz: port 2(vnet2) entering disabled state
Mar  2 14:53:54 leo01 libvirtd: 14:53:54.333: error : qemudReadLogOutput:816 : internal error Process exited while reading console log output
Mar  2 14:53:54 leo01 libvirtd: 14:53:54.333: error : qemudWaitForMonitor:1103 : internal error unable to start guest: libvir: Security Labeling error : error calling aa_change_profile()#012libvir: QEMU error : internal error Failed to set security label#012
Mar  2 14:53:54 leo01 libvirtd: 14:53:54.471: error : virRun:833 : internal error '/usr/bin/virt-aa-helper -R -u libvirt-009c6a05-d841-2b80-51ac-fc940f0000f4' exited with non-zero status 1 and signal 0: libvir: error : internal error '/sbin/apparmor_parser -R /etc/apparmor.d/libvirt/libvirt-009c6a05-d841-2b80-51ac-fc940f0000f4' exited with non-zero status 234 and signal 0: /sbin/apparmor_parser: Unable to remove "libvirt-009c6a05-d841-2b80-51ac-fc940f0000f4".  Profile doesn't exist#012virt-aa-helper: error: failed to run apparmor_parser#012
Mar  2 14:53:54 leo01 libvirtd: 14:53:54.471: error : virSecurityReportError:108 : could not remove profile for 'libvirt-009c6a05-d841-2b80-51ac-fc940f0000f4'
Mar  2 14:53:54 leo01 kernel: [84139.330434] type=1505 audit(1267538034.463:52): operation="profile_remove" info="failed: profile does not exist" pid=11213 name=libvirt-009c6a05-d841-2b80-51ac-fc940f0000f4 namespace=default