Le problème est lié au fait que par défaut, le paquet Debian/Ubuntu "locales" ne génère que les locales en UTF-8, mais pas les version ISO8859 pour les alphabets latins. Il faut donc faire un peu ménage dans tout ça.

Au préalable, on vérifie que le paquet "locales" est bien installé:

sudo apt-get install locales

On n'échappera pas au message déjà cité plus haut. Ensuite, on reconfigure le paquet pour qu'il génère les locales UTF-8

sudo dpkg-reconfigure locales

Et enfin la commande qui permettra de générer, en l'occurence pour les francophones le paquet fr_FR@euro, alias du paquet fr_FR@ISO-8859-15:

sudo locale-gen fr_FR@euro