Demorou mais de um ano para não me dar conta disso, mas finalmente descobri.
Faça estas coisas:
- Faça login no MSN em uma caixa do Windows. (Eu sei, isso me machucou também)
- Encontre esse usuário e exclua-o. A conta dele provavelmente está fechada de qualquer maneira
- Seu Pidgin deve funcionar bem novamente.
Eu não pude, durante minha vida, corrigir esse problema apenas com o Pidgin.