On a Debian Lenny server I changed the default locale from en_US.UTF-8 to en_US.ISO-8859-15 to be able to edit some files with European Umlauts. 

The setting has changed on the fly and I was able to view and edit such files perfectly with vim. But some scripts couldn't find that new locale, as they showed perl errors like this:

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
        LANGUAGE = (unset),
        LC_ALL = (unset),
        LANG = "en_US.ISO-8859-15"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory

This error comes from the command update-locale and as it points out, the file or directory for the defined locale couldn't be found.

It can be resolved by installing the package locales-all (by default only 'locales' is installed) which downloads additional locale files. The command update-locale worked fine just after.