Acabei de ter o mesmo problema.
Enquanto usava o Ubuntu 11.10 e tentava instalar o idioma francês, recebi o erro:
Package [dbus.String(u'thunderbird')] is already installed
Como seria muito demorado desinstalar, reinstalar e reconfigurar o Thunderbird (como indicado em outra resposta), procurei uma solução diferente.
O que eu descobri foi que eu tinha algumas atualizações pendentes no utilitário "Update Manager".
Tudo o que eu precisava fazer era lançar o "Gerenciador de Atualizações" e clicar em "Instalar Atualizações".
Depois disso, conseguiu instalar o pacote de idioma francês.
Então, minha dica é: verifique se há atualizações pendentes antes de tentar instalar um novo pacote de idiomas .