As movimentações interestaduais devem utilizar um Código Fiscal de Operação (CFOP) iniciadas por 2 ou 6, que classifica operações fora do estado. Desta forma a UF do emitente deve ser diferente da UF do destinatário.
Como Resolver
Na tela principal de lançamento da NF-e, verifique se a operação utilizada está com um CFOP iniciado por 2 ou 6.
(warning) O CFOP iniciado por:
2 xxx - Refere-se a compras ou entradas de fora do estado.
6 xxx - Refere-se a vendas ou saídas para fora do estado.
Também é necessário que o destinatário da NF-e tenha a UF distinta do emitente.
Manual de Orientação do Contribuinte 2015 - http://www.nfe.fazenda.gov.br/portal/listaConteudo.aspx?tipoConteudo=33ol5hhSYZk=