1 - Verifique no Cadastro do Destinatário se o campo Código UF consta em branco. Este campo deve estar preenchido.
2 - Verifique no Cadastro do Destinatário se o campo Estado está em minúsculo. Este campo deve estar Maiúsculo.

Essas orientações valem tanto para o Cadastro do Destinatário, como também para o Cadastro da Transportadora na Nota.