Qual a versão do Ubuntu vc está usando? Se for uma anterior à 5.10, aconselharia-lhe a atualizá-la.
Não sei qual a origem desse problema no Ubuntu, já que ainda não o estou usando efetivamente, faltando apenas solucionar um problema de conexão. Mas tive o mesmo problema ao instalar o msn 0.95 no Kurumin (versões 4.0 e 5.0). Nestas versões estava ocorrendo um conflito entre os pacotes stable e testing/unstable, o que me levou a deixar no /etc/fstab apenas mirrors para pacotes stable. Logo, não conseguia atualizar certas bibliotecas, como a libstdc++6, cujas versões mais recentes só eram disponibilizadas na versão testing (pelo que eu entendi, foi isso que ocorreu).
O que vc poderia estar fazendo é consultar o
www.apt-get.org e procurar pelos pacotes pendentes, acrescentando os links sugeridos no respectivo site ao seu arquivo /etc/fstab, bem como editá-lo, descomentando, ou incluindo as linhas contendo endereços de pacotes testing. No entanto, isso pode gerar os conflitos que mencionei acima.
No mais, a sugestão mais segura é continuar com a versão do amsn 0.94.
Um outro modo de conseguir os pacotes pendentes é ir no repositório de pacotes do Debian (faça uma busca por debian +packages no Google). Mas também será complicado, pois, ao baixar o .deb do pacote requerido, quando for tentar instalar, novas dependências surgirão e não será muito divertido ter de procurar uma por uma. Ainda assim, acredito, correrá o risco de criar novos conflitos de pacotes no micro.
Enfim, se quer usar pacotes mais recentes, acho mesmo que deve procurar usar a versão mais nova do sistema.