dpkg-reconfigure locales doesn’t seem ask what locales you want to enable anymore (ubuntu 8.10), whatever the priority of questions you set in debconf…

The locales to be generated are listed in this file : /var/lib/locales/supported.d/local

Just add your locales there, then do a dpkg-reconfigure locales, it should generate you new locales :

skanx@tipica:~$ cat /var/lib/locales/supported.d/local
en_US.UTF-8 UTF-8
fr_FR UTF-8

skanx@tipica:~$ sudo dpkg-reconfigure locales
Generating locales…
en_US.UTF-8… up-to-date
fr_FR.UTF-8… done