O Gaim, recentemente, tinha um bug ao se conectar com a rede msn. A solução é atualizar para a versão 2.0 beta, que funciona redondinha. A melhor maneira de atualizar o Gaim é pelo Automatix. Tarefa de casa: pesquise aqui no fórum sobre o Automatix.
Uma dica: ao usar o Automatix, instale
apenas o Gaim. Acho que é bug, mas, quando se tenta instalar mais coisas com ele, o Gaim não é atualizado.