Não fique conectando no outro, porque se não seu cache doas navegadores vai ficar configurações do outro provedor ae da esse problema todo, limpe seu cache, cookies e etc dos navegadores.
Mais pelo que vc ta citando, o problema é no roteamento só pode, sua maquina esta cheia de configurações do antigo provedor de banda larga, a se fazer é digitar os comandos passados a cima para limpar tudo e por as configurações de DNS manuais, para todos os Micros, tanto o seu quanto o dele, vc também pode testar ligando direto no cabo no modem dele para ver o que ocorre.