Après avoir installé Ubuntu 9.04 (Jaunty Escalope ou quelquechose comme ça). J'ajoute un dépôt dans Synaptic et je cherche le paquet pour lequel j'ai installé ce dépôt : RIEN
apt-get install "le-nom-du-paquet" et ça marche ! 
Quelques essais avec d'autres dépôts me confirme la chose : il y a un problème.
Et comme dit mon maître, quand il y a un problème, il y a une solution 
Faire :
sudo update-apt-xapian-index
Et c'est reparti comme avant.