O problema foi com a virtualização aninhada (já que o OpenStack usa seu próprio hipervisor). Eu pude superar esse problema como habilitar hipervisor (KVM no meu caso) para virtualização aninhada. E depois de criar interfaces de ponte sobre a interface ethernet, pude usar a rede NAT no KVM como rede pública para as VMs no OpenStack.