Antes da API da Nuvem Fiscal enviar o XML para o provedor da prefeitura, realizamos a validação de toda a sua estrutura. A princípio, não há nada de errado de acordo com os schemas fornecidos pelo próprio provedor. Assim, será necessário entrar em contato com o suporte da prefeitura e encaminhar o nosso XML para eles analisarem.
Só para dar um retorno, o problema estava no campo CNAE no nosso sistema que não tinha sido preenchido pelo usuário, depois de informar a nota aprovou certinho.