Foi visto junto ao desenvolvimento que apenas duas situações poderiam levar a essa rejeição:
1) Ou o cliente não foi habilitado junto a Sefaz para emissão
2) Ou pode haver algum problema com o certificado (troca, por exemplo).
As duas hipótese acima foram vistas, conferidos os dados da empresa e estava tudo ok.
Então, foi consultado o Sintegra, e obtivemos a situação cadastral como: Suspenso.

O cliente foi orientado entrar em contato com a SEFAZ para verificar sua situação, conforme mostra a consulta do SINTEGRA.