Depois de muita dificuldade para entrar no MSN pelo Ubuntu 9.04 usando o Pidgin, a solução que garimpei na net foi instalar o protocolo WLM através do pacote msn-pecan. Aos que estiverem com dificuldade e resolverem testar:

sudo apt-get install msn-pecan

Bem, essa é minha primeira dica e espero ter ajudado.

Referência: https://lists.ubuntu.com