Created attachment 831888 [details]
OVS logs

VXLAN is not working,
DHCP request is not going out of the compute node to the DHCP server,
iptables is off and TCPDUMP doesn't show packets egress the compute node

Created attachment 831960 [details]
OVS logs working with GRE

* Setup RHOS 4.0 latest repos (2013-12-12.1)
* Installed using Packstack: One controller (Everything on it), 2 additional * compute nodes. All 3 are VMs on different physical hosts running RHEL 6.5
* Disabled firewall on controller
* SELinux is in permissive mode
* Disabled firewall on compute nodes for VNC

* In /etc/neutron/plugin.ini, for all hypervisors:
  Under [OVS]
  tenant_network_type=vxlan
  tunnel_type=vxlan
  Under [AGENT]
  tunnel_types=vxlan

* On all hypervisors:
  ovs-vsctl emer-reset && service openstack-openvswitch-agent restart

* Deleted network that was created as GRE, recreated it

I have connectivity between instances running on different hypervisors.

You shouldn't need to disable the firewall, but probably do need to open UDP port 4789 on all nodes where openvswitch-agent runs for VXLAN.

Oh absolutely - I'm not suggesting to disable any firewalls, I'm just stating what steps I took to make it to work.

I have retested VXLAN on latest puddle with the same configuration as Assaf mentioned.

Traffic works between two VMs on different hosts 
Traffic works between VM and router and floating ip is used to gate the internet

openstack-neutron-2013.2-16.el6ost.noarch
openstack-neutron-openvswitch-2013.2-16.el6ost.noarch
kernel-2.6.32-431.1.2.el6.x86_64 

attached PCAP