Problemas com IM no Linux

Olá, estou precisando de ajuda aqui.
Meu padrao alterou toda a rede em que trabalhamos, adicionando um novo link de 2Mb e, desde então, não consigo conectar mais nenhum IM.
Sempre usei MSN e GTalk via Gaim nesta rede e funcionava, mas agora não funciona mais, também testei com o Kopete e dá na mesma.
O estranho é que as máquinas Windows ligadas a rede estes funcionam normalmente.

Uma vez que uso os mesmo protocolos, o que pode haver de diferença para o MSN e GTalk funcionarem no Win e não funcionarem no meu GNU/Linux?

ps.: uso um Debian Etch.