J'ai fixé l'adresse DNS à une conseillée par Orange (trouvée dans ce tuto pour ceux que ça intéresse) dans wicd, et...
Wouah !!!

Quand je penses qu'avant, un "yaourt -Su --aur" prenait 2-3 minutes, contre 15 secondes maintenant...

Bref, je vous remercie, les gars !
Vous avez été super efficaces, comme d'hab'.

EDIT :
Juste une question qui me vient à l'esprit à l'instant : Pour l'instant, je suis chez moi, mais en dehors des vacances, mon portable est connecté au réseau local de mon internat, et la connexion passe par un proxy.
Faudra-t-il que je change les serveurs DNS ? Si oui, pour lesquels ? Ceux du FAI du réseau (Free) ?