We had the same problem and it turned out to be a network problem. The machines couldn't be pinged because the floating IPs were no tied to any interface. It was solved by adding PUBLIC_INTERFACE=interfacename to local.conf (or nova.conf if ypu're not using devstack)