When I run tcpdump on the vm im running Linux/Openstack on, and ping the openstack launched instance, I see arp requests for the launced instance but no arp reply's (which probably result in the no route to host errors).