Um cliente meu passou por exatamente esse problema, mudando apenas a Operadora.
Resolveu desabilitando a auto negotiation na interface com a Operadora.