Esta pode ser sua rede móvel tentando bloquear aplicativos de mensagens instantâneas (a maioria dos contratos de celular estipula que você concorda em não usar conexões de dados para mensagens instantâneas, pois afeta a capacidade das redes de ganhar grandes quantias de dinheiro enviando mensagens por SMS ) ou pode ser que o protocolo que você está usando reaja mal à maior latência da rede móvel (embora essa opção seja menos provável) ou à combinação de alta latência e gerenciamento de tráfego pelo provedor de telefonia celular.
Eu tenho esse problema com meu netbook, também executando o Ubuntu 9.04 e usando o Pidgin. Quando conectado a redes sem fio está tudo bem, mas quando conectado através do meu celular (atualmente na rede da Vodafone no Reino Unido) eu geralmente não consigo me conectar às minhas contas do MSN ou do Yahoo. Eu ainda tenho que provar se isso é devido ao Vodaphone ou algum problema de rede mais geral (em algum momento eu pretendo testar através do OpenVPN, ou similar, para ver se isso faz alguma diferença, pois o gerenciamento de tráfego da VF não verá a diferença entre Conexões de mensagens instantâneas e qualquer outra coisa, embora a própria VPN possa ser bloqueada ou ter um formato de tráfego em inutilidade).
Além disso, conforme sugerido pela Roland, pode ser um problema de configuração. Para descartar problemas de rede, teste se você ainda tem problemas para acessar os serviços de MI quando sua máquina tiver uma conexão com fio ou sem fio. Também pode valer a pena tentar outros clientes de mensagens instantâneas para descartar o problema específico do Pidgin. Também dependendo de qual protocolo de mensagens instantâneas você está tentando usar, você pode descobrir que existe um plug-in alternativo que lida melhor por padrão - por exemplo, "pecan" é um plug-in alternativo para contas do MSN / WindowsLive.