I have hit this bug repeatedly on creating new instance on a compute-node on which already 4 instances exist.
Resource-wiseless than 10% of the hypervisor has been used by the existing instances.
Any new instance creation is failing at the same place as per the log trace.  I have attached the log for my instance named 'AGAIN'

Below is the log snippet:
=======================

2015-06-09 08:03:47.153 19692 WARNING nova.virt.libvirt.driver [-] Timeout waiting for vif plugging callback for instance b8c3a1dc-8780-4495-8a7e-3f03f14c8475
2015-06-09 08:03:47.363 19692 DEBUG nova.virt.libvirt.vif [-] vif_type=ovs instance=Instance(access_ip_v4=None,access_ip_v6=None,architecture=None,auto_disk_config=False,availability_zone=None,cell_name=None,cleaned=True,config_drive='',created_at=2015-06-09T14:58:40Z,default_ephemeral_device=None,default_swap_device=None,deleted=False,deleted_at=None,disable_terminate=False,display_description='AGAIN',display_name='AGAIN',ephemeral_gb=0,ephemeral_key_uuid=None,fault=<?>,host='f3-compute-2.noiro.lab',hostname='again',id=77,image_ref='82cd7cee-ade0-43b2-94ac-b7cb8c0c941b',info_cache=InstanceInfoCache,instance_type_id=1,kernel_id='',key_data=None,key_name=None,launch_index=0,launched_at=None,launched_on='f3-compute-2.noiro.lab',locked=False,locked_by=None,memory_mb=4096,metadata={},node='f3-compute-2.noiro.lab',numa_topology=None,os_type=None,pci_devices=PciDeviceList,power_state=0,progress=0,project_id='26acdadf476e49e78172ef6f0595f9a1',ramdisk_id='',reservation_id='r-51nqu02g',root_device_name='/dev/vda',root_gb=40,scheduled_at=None,security_groups=SecurityGroupList,shutdown_terminate=False,system_metadata={image_base_image_ref='82cd7cee-ade0-43b2-94ac-b7cb8c0c941b',image_container_format='bare',image_disk_format='qcow2',image_min_disk='40',image_min_ram='0',instance_type_ephemeral_gb='0',instance_type_flavorid='3',instance_type_id='1',instance_type_memory_mb='4096',instance_type_name='m1.medium',instance_type_root_gb='40',instance_type_rxtx_factor='1.0',instance_type_swap='0',instance_type_vcpu_weight=None,instance_type_vcpus='2',network_allocated='True'},task_state='spawning',terminated_at=None,updated_at=2015-06-09T14:58:44Z,user_data=None,user_id='3fd8184442334332be33cdfe5b57b1ae',uuid=b8c3a1dc-8780-4495-8a7e-3f03f14c8475,vcpus=2,vm_mode=None,vm_state='building') vif=VIF({'profile': {}, 'ovs_interfaceid': u'8d51f6bd-6a8b-43a0-9d86-b8384225eab5', 'network': Network({'bridge': 'br-int', 'subnets': [Subnet({'ips': [FixedIP({'meta': {}, 'version': 4, 'type': 'fixed', 'floating_ips': [], 'address': u'5.5.5.7'})], 'version': 4, 'meta': {'dhcp_server': u'5.5.5.3'}, 'dns': [], 'routes': [Route({'interface': None, 'cidr': u'5.5.5.0/24', 'meta': {}, 'gateway': IP({'meta': {}, 'version': 4, 'type': 'gateway', 'address': u'5.5.5.1'})})], 'cidr': u'5.5.5.0/28', 'gateway': IP({'meta': {}, 'version': 4, 'type': 'gateway', 'address': u'5.5.5.1'})})], 'meta': {'injected': False, 'tenant_id': u'26acdadf476e49e78172ef6f0595f9a1'}, 'id': u'4659e62b-f4fd-43ac-b18a-5ef30fac028e', 'label': u'l2p_demo_same_ptg_l2p_l3p_bd'}), 'devname': u'tap8d51f6bd-6a', 'vnic_type': u'normal', 'qbh_params': None, 'meta': {}, 'details': {u'port_filter': False, u'ovs_hybrid_plug': False}, 'address': u'fa:16:3e:61:6a:e8', 'active': False, 'type': u'ovs', 'id': u'8d51f6bd-6a8b-43a0-9d86-b8384225eab5', 'qbg_params': None}) unplug /usr/lib/python2.7/site-packages/nova/virt/libvirt/vif.py:688
2015-06-09 08:03:47.366 19692 DEBUG nova.virt.driver [-] Emitting event <LifecycleEvent: 1433862227.36, b8c3a1dc-8780-4495-8a7e-3f03f14c8475 => Stopped> emit_event /usr/lib/python2.7/site-packages/nova/virt/driver.py:1299
2015-06-09 08:03:47.366 19692 INFO nova.compute.manager [-] [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] VM Stopped (Lifecycle Event)
2015-06-09 08:03:47.401 19692 DEBUG nova.compute.manager [-] [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] Synchronizing instance power state after lifecycle event "Stopped"; current vm_state: building, current task_state: spawning, current DB power_state: 0, VM power_state: 4 handle_lifecycle_event /usr/lib/python2.7/site-packages/nova/compute/manager.py:1150
2015-06-09 08:03:47.405 19692 DEBUG nova.objects.instance [-] Lazy-loading `system_metadata' on Instance uuid b8c3a1dc-8780-4495-8a7e-3f03f14c8475 obj_load_attr /usr/lib/python2.7/site-packages/nova/objects/instance.py:579
2015-06-09 08:03:47.438 19692 INFO nova.compute.manager [-] [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] During sync_power_state the instance has a pending task (spawning). Skip.
2015-06-09 08:03:47.444 19692 DEBUG nova.openstack.common.processutils [-] Running cmd (subprocess): mv /var/lib/nova/instances/b8c3a1dc-8780-4495-8a7e-3f03f14c8475 /var/lib/nova/instances/b8c3a1dc-8780-4495-8a7e-3f03f14c8475_del execute /usr/lib/python2.7/site-packages/nova/openstack/common/processutils.py:161
2015-06-09 08:03:47.453 19692 DEBUG nova.openstack.common.processutils [-] Result was 0 execute /usr/lib/python2.7/site-packages/nova/openstack/common/processutils.py:195
2015-06-09 08:03:47.454 19692 INFO nova.virt.libvirt.driver [-] [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] Deleting instance files /var/lib/nova/instances/b8c3a1dc-8780-4495-8a7e-3f03f14c8475_del
2015-06-09 08:03:47.454 19692 INFO nova.virt.libvirt.driver [-] [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] Deletion of /var/lib/nova/instances/b8c3a1dc-8780-4495-8a7e-3f03f14c8475_del complete
2015-06-09 08:03:47.495 19692 ERROR nova.compute.manager [-] [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] Instance failed to spawn
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] Traceback (most recent call last):
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]   File "/usr/lib/python2.7/site-packages/nova/compute/manager.py", line 2288, in _build_resources
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]     yield resources
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]   File "/usr/lib/python2.7/site-packages/nova/compute/manager.py", line 2158, in _build_and_run_instance
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]     block_device_info=block_device_info)
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]   File "/usr/lib/python2.7/site-packages/nova/virt/libvirt/driver.py", line 2635, in spawn
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]     block_device_info, disk_info=disk_info)
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]   File "/usr/lib/python2.7/site-packages/nova/virt/libvirt/driver.py", line 4579, in _create_domain_and_network
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]     raise exception.VirtualInterfaceCreateException()
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] VirtualInterfaceCreateException: Virtual Interface creation failed
2015-06-09 08:03:47.495 19692 TRACE nova.compute.manager [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475]
2015-06-09 08:03:47.496 19692 AUDIT nova.compute.manager [req-db08580d-efec-4377-baa5-e98e5868c055 None] [instance: b8c3a1dc-8780-4495-8a7e-3f03f14c8475] Terminating instance