Solução:

Esse problema pode ocorrer por dois motivos:

1 - Os Dados do Destinatário podem estar incorretos; E nesse caso, não seria apenas a UF, mas sim todo o Endereço.

2 - O Destino da Operação (Estadual, Interestadual ou Exterior) pode estar incorreto.

Primeira situação: 

Verifique se sua Operação é Estadual (Interna), então apenas os Dados do Destinatário estão incorretos. Nesse caso, você deve corrigir o Endereço do Destinatário. Sempre em uma Operação Estadual com Consumidor Normal (indFinal = 0), a UF do Destinatário deve ser igual a UF do Emitente.

Segunda Situação:

Verifique se sua Operação é Interestadual (idDest = 2), muito provavelmente os Dados do Destinatário estarão corretos. Você precisará fazer duas alterações nesse caso:

1. Alterar o campo idDest de 1 para 2;

2. Alterar o CFOP de todos os Produtos. No caso de Operação Interestadual, o CFOP deve obrigatoriamente iniciar com o dígito 6 (seis).

Existe algumas exceções de regras,como:

 - A regra de validação 773, não se aplica, se a tag UFCons foi informada com a mesma UF do emitente;
 - A regra de validação 773 não se aplica se informada UF do local de entrega igual à UF do emitente e não informada UF do local de retirada;
 - A regra de validação 773 não se aplica se informada UF do local de retirada igual à UF do destinatário e não informada UF do local de entrega;
 - A regra de validação 773 não se aplica se informadas UF do local de entrega e UF do local de retirada iguais entre si.

Feita a correção, basta reenviar a NF-e.