O que é? A rejeição acontece quando a NF-e está sendo emitida com o CFOP iniciado por 1 ou 5 (operações estaduais) e o destino da operação (idDest) é de outro estado.
Os CFOPs iniciados em 5 são de operação interna (para dentro do estado), enquanto os CFOPs iniciados em 6 são de operação interestadual.

Video: Como corrigir? Assista o vídeo.
Passo 1: Clique no menu “Fiscal > Documentos fiscais” .

Passo 2: Selecione a data em que a nota fiscal foi emitida.

Passo 3: Após selecionar a data, clique em “Filtrar (Enter)” .

Passo 4: Selecione a nota com rejeição e depois logo abaixo clique no botão ALTERAR (F2)

Passo 5: Clique no aba ITENS (CRTL+2).

Passo 6: Podemos notar que o NOP (CFOP) que está informado 5102 (iniciando com 5), porém o nosso cliente é de outro estado, o correto seria iniciado com 6.
(Os CFOPs iniciados em 5 são de operação interna (para dentro do estado), enquanto os CFOPs iniciados em 6 são de operação interestadual.).

Passo 7: Na parte inferior, clique em ALTERAR NOP (F7).

Passo 8: Selecione a NOP correspondente, neste exemplo a 610201 (que inicia com 6, pois o cliente é de outro estado). Depois é só clicar em CONFIRMAR (F1).

Pronto, agora só clicar em TRANSMITIR (F2) que a nota será enviada com sucesso.