Quando ocorreu esse problema, teve-se o cuidado de verificar diversas coisas:
1) A licença existia
2) No portal a empresa habilitada para a licença era realmente a do cliente
3) Fizemos o download da licença
4) Verificamos CNPJ, site da Sefaz, etc.
Tudo estava certo. Então envolvemos um desenvolvedor e, foi descoberto que o caminho da licença estava incorreto ( alguém havia mexido).