CEP não encontrado quando cliente se cadastra

Olá. Fiz testes para calcular o frete antes de fazer um cadastro como cliente na minha loja e funciona.
Quando porém vou colocar o CEP na hora de fazer o cadastro, aparece uma mensagem falando que não encontrou o CEP - e depois ele reconhece o cep. Alguém passou por iss?