Pour être plus précis, quand je mets à jour la liste des paquets par "apt-get update", j'obtiens (entre autre) le message d'erreur :
Impossible de récupérer http://ppa.launchpad.net/alexis.bienvenue/amc-stable/

J'ai l'impression que le problème vient de là.

OK, problème résolu : en fait la verison 1.3.0 n'est pas dans le dépôt amc-stable mais dans le dépôt amc.

Pour ceux qui seraient confrontés au même problème, voilà la démarche (sous ubuntu en tout cas) :

sudo apt-get-repository ppa:alexis.bienvenue/amc
sudo apt-get update
sudo apt-get install auto-multiple-choice

J'attendais un peu pour voir si il y avait un gros problème, mais la version 1.3.0 est maintenant dans amc-stable.