Falha
Conforme resposta da SEFAZ de MG, a mesma entrou em produção com a NT 2013/14, aonde a rejeição de ‘Mensagem Não Catalogada 519’ se refere ao CFOP para CTe.
Solução
Esta mensagem conforme a pergunta, se refere ao CFOP no CTE que esta inválido.
Outras informações
Fonte: Paulo Roberto Almeida, Petterson Grahl Ferreira