Amigo, segue o raciocínio nessa ordem:
Primeiro você criar as "Zonas" que são regiões do País: Centro-oeste, Sul, Nordeste ... : Localização > Regiões
Criar os estados, e selecione os estados para essas Zonas : Localização > Estados
Ative o país Brasil : Localização > País
Testes:
Faça cadastros de clientes diferentes do CEP de regiões distantes da sua localização;
Compra de produtos com peso, dimensões diferentes;
Verifique se o seu módulo dos correios esta correto. Lembrando que o módulo gratuito para consulta no site do Correios, são as duas encomendas: PAC e Sedex, restante é necessário contrato com eles. É só ligar para o correio ai e solicitar o contrato por e-mail.
Poderá haver outras configurações...