Eu sei que é tarde para responder, mas postar como isso pode ajudar os outros. Eu tive o mesmo problema e descobri enquanto instalava nova-network e nova-api-metadata, o pacote nova-api está sendo desinstalado, o que era estranho. Depois de reinstalar o problema do pacote nova-api resolvido.
(Ubuntu 14.04, versão openstack kilo)