I've run into this problem a few times now.

The first time I solved it by copying /usr/lib/locale and /usr/share/locale from backups, but this has the disadvantage of reintroducing cruft from now-uninstalled packages.

I just stopped here to point out that pali's gem of an overlooked one-liner from this thread saved my *** this time around:
I ran it after configuring /etc/locale.gen and running locale-gen. Incidentally, I had also followed starkwiz's advice from another thread: to re-install the "posix-locales" package, create "/etc/osso-af-init/locale", and populate it with the desired locale system variables. I'm not sure if this latter was really any help or not, but the problem hadn't entirely gone away until after running pali's command which reinstalls all packages which include locale data.