Erro "O Teredo não pode se qualificar" e "Conectividade do servidor: Bloqueado"

Normalmente essas informações ficam na aba WAN do modem, (o que está recebendo a internet não o roteador WIFI). Dependendo eles podem te dar a informação escancarada ou não, eles podem te dizer algo como IP Dinâmico(Nat 2) ou IP fixo(NAT3) .  

Ligue para o provedor e pergunte a eles.

Usuários leigos não conseguem saber a diferença tão facilmente por causa da quantidade de termo técnico, mas é por esse tipo de coisa que alguns sites ou serviços como jogos online ou chamadas ao vivo não funcionam na internet de algumas pessoas. 

É bom você ter muita paciência se pegar algum atendente que não manja muito disso.

Obrigado pela atenção, espero que ele possa me ajudar!

Certo, desconfiei de possível problema de duplo NAT mas também não é o caso. Lucas infelizmente fico sem ideias de como continuar lhe ajudando, vou liberar sua pergunta para que outro consultor possa tentar ajudá-lo. Obrigado.

Como faço para saber qual é minha NAT?

Verifique a sua NAT, esses tipos de problemas são um pouco "normais", mas normalmente tudo é solucionado com o botão corrigir. Quando não significa que sua conexão está muito ruim ou tem outros problemas. 

Quando o TEREDO não pode se qualificar significa que o seu computador ou a rede não tem permissão para utilizar as portas necessárias para estabelecer uma conexão seja TCP ou UDP. 

AS NATS SÃO:

NAT 1- NAT do tipo 1 é aberta, ela tem um IP publico único, valido e tem todas as portas abertas, podendo se comunicar com NAT 1 2 e 3, a consequência de ter uma NAT do tipo 1 é que o seu computador não precisa requisitas uma chamada internamente na rede, alguém pode lhe enviar.

Imagine que você está em casa e ela tem varias janelas, todas abertas e sem moderação, alguém pode jogar uma bomba dentro dela sem que o pedido tenha vindo de dentro.

NAT-2 A NAT do tipo 2 é moderada, ele apresenta a gigantesca maioria das portas abertas e um IP publico valido, pode conversar com  NAT 1 e 2, ao contrario da anterior essa tem as portas moderadas e caso o trafego exceda uma das regras do firewall interno a comunicação pode ser encerrada, também não aceita conexões que foram requisitadas internamente.

NAT3 e CGNAT- A NAT 3 por regra é a mais restrita e não apresenta um IP publico apenas um privado, (NAT 1 e 3) o IP publico é atribuído apenas na saída do servidor do provedor, da pra colocar milhares de pessoas com o mesmo IP, o que pode ser um problema muito serio em sites que monitoram o trafego vindo dos IPS, os servidores podem recusar a conexão. 

Isso nem sempre é uma regra, a CGNAT é parecida com a NAT 3 mas não é a mesma coisa, em fim invés de começar as coisas mais complicadas, verifique se você está com NAT3 e ligue pra o provedor pra eles lhe darem um IP publico valido seja do tipo 2 ou 1 (não recomendo). Pode ser que eles lhe neguem pois sim eles podem fazer isso, caso eles estejam usando CGNAT nem adianta ligar pois é uma questão de arquitetura de rede ou seja é irreversível.