`sudo locale-gen "$LANG"` is the answer when everyone's yelling about "can't set the locale; make sure $LC_* and $LANG are correct" and apt-get's perl calls are throwing warnings.