I just hit a similar issue (note: I didn't make a typo Phil mentioned in comment #5) while I was testing on Fedora 20 with Neutron+ML2+OVS+GRE with IceHouse release . My setup is more completely described here[1].

---------------------------------
.
.
.
     2014-05-13 07:06:32.123 29455 TRACE nova.compute.manager [instance: 950de10f-4368-4498-b46a-b1595d057e38]   File "/usr/lib/python2.7/site-packages/nova/virt/libvirt/driver.py", line 3431, in to_xml
      2014-05-13 07:06:32.123 29455 TRACE nova.compute.manager [instance: 950de10f-4368-4498-b46a-b1595d057e38]     disk_info, rescue, block_device_info)
      2014-05-13 07:06:32.123 29455 TRACE nova.compute.manager [instance: 950de10f-4368-4498-b46a-b1595d057e38]   File "/usr/lib/python2.7/site-packages/nova/virt/libvirt/driver.py", line 3247, in get_guest_config
      2014-05-13 07:06:32.123 29455 TRACE nova.compute.manager [instance: 950de10f-4368-4498-b46a-b1595d057e38]     flavor)
      2014-05-13 07:06:32.123 29455 TRACE nova.compute.manager [instance: 950de10f-4368-4498-b46a-b1595d057e38]   File "/usr/lib/python2.7/site-packages/nova/virt/libvirt/vif.py", line 384, in get_config
      2014-05-13 07:06:32.123 29455 TRACE nova.compute.manager [instance: 950de10f-4368-4498-b46a-b1595d057e38]     _("Unexpected vif_type=%s") % vif_type)
      2014-05-13 07:06:32.123 29455 TRACE nova.compute.manager [instance: 950de10f-4368-4498-b46a-b1595d057e38] NovaException: Unexpected vif_type=binding_failed
      2014-05-13 07:06:32.123 29455 TRACE nova.compute.manager [instance: 950de10f-4368-4498-b46a-b1595d057e38] 
      2014-05-13 07:06:32.846 29455 ERROR oslo.messaging.rpc.dispatcher [-] Exception during message handling: Unexpected vif_type=binding_failed
---------------------------------

  [1] https://www.redhat.com/archives/rdo-list/2014-May/msg00060.html


ml2_config.ini and nova.conf
------------------------------------

ml2 plugin:

    $ cat /etc/neutron/plugin.ini | grep -v ^$ | grep -v ^#
    [ml2]
    type_drivers = gre
    tenant_network_types = gre
    mechanism_drivers = openvswitch
    [ml2_type_flat]
    [ml2_type_vlan]
    [ml2_type_gre]
    tunnel_id_ranges = 1:1000
    [ml2_type_vxlan]
    [securitygroup]
    firewall_driver = neutron.agent.linux.iptables_firewall.OVSHybridIptablesFirewallDriver
    enable_security_group = True

nova.conf:

    $ cat /etc/nova/nova.conf | grep -v ^$ | grep -v ^#
    [DEFAULT]
    logdir = /var/log/nova
    state_path = /var/lib/nova
    lock_path = /var/lib/nova/tmp
    volumes_dir = /etc/nova/volumes
    dhcpbridge = /usr/bin/nova-dhcpbridge
    dhcpbridge_flagfile = /etc/nova/nova.conf
    force_dhcp_release = True
    injected_network_template = /usr/share/nova/interfaces.template
    libvirt_nonblocking = True
    libvirt_use_virtio_for_bridges=True
    libvirt_inject_partition = -1
    #libvirt_vif_driver=nova.virt.libvirt.vif.LibvirtGenericVIFDriver
    #libvirt_vif_driver=nova.virt.libvirt.vif.LibvirtHybridOVSBridgeDriver
    #iscsi_helper = tgtadm
    sql_connection = mysql://nova:nova@192.169.142.97/nova
    compute_driver = libvirt.LibvirtDriver
    libvirt_type=qemu
    rootwrap_config = /etc/nova/rootwrap.conf
    auth_strategy = keystone
    firewall_driver=nova.virt.firewall.NoopFirewallDriver
    enabled_apis = ec2,osapi_compute,metadata
    my_ip=192.169.142.168
    network_api_class = nova.network.neutronv2.api.API
    neutron_url = http://192.169.142.97:9696
    neutron_auth_strategy = keystone
    neutron_admin_tenant_name = services
    neutron_admin_username = neutron
    neutron_admin_password = fedora
    neutron_admin_auth_url = http://192.169.142.97:35357/v2.0
    linuxnet_interface_driver = nova.network.linux_net.LinuxOVSInterfaceDriver
    firewall_driver = nova.virt.firewall.NoopFirewallDriver
    security_group_api = neutron
    rpc_backend = nova.rpc.impl_kombu
    rabbit_host = 192.169.142.97
    rabbit_port = 5672
    rabbit_userid = guest
    rabbit_password = fedora
    glance_host = 192.169.142.97
    [keystone_authtoken]
    auth_uri = http://192.169.142.97:5000
    admin_tenant_name = services
    admin_user = nova
    admin_password = fedora
    auth_host = 192.169.142.97
    auth_port = 35357
    auth_protocol = http
    signing_dirname = /tmp/keystone-signing-nova