Problem

On a fresh installation of Debian 8, 9, 10 and maybe also other versions you can get the following error:

    The programs included with the Debian GNU/Linux system are free software;
    the exact distribution terms for each program are described in the
    individual files in /usr/share/doc/*/copyright.

    Debian GNU/Linux comes with ABSOLUTELY NO WARRANTY, to the extent
    permitted by applicable law.
    _________________________________________________________
    WARNING! Your environment specifies an invalid locale.
     The unknown environment variables are:
       LC_CTYPE=UTF-8 LC_ALL=
     This can affect your user experience significantly, including the
     ability to manage packages. You may install the locales by running:

     sudo dpkg-reconfigure locales

     and select the missing language. Alternatively, you can install the
     locales-all package:

     sudo apt-get install locales-all

    To disable this message for all users, run:
      sudo touch /var/lib/cloud/instance/locale-check.skip
    _________________________________________________________

If you follow the instructions and run the command dpkg-reconfigure locales and then select your desired locales, you will still get an error: (In my case I selected en_US.UTF-8 and es_es.UTF-8)

root@localhost:~# dpkg-reconfigure locales
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LC_CTYPE = "UTF-8",
    LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to a fallback locale ("en_US.UTF-8").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
/usr/bin/locale: Cannot set LC_CTYPE to default locale: No such file or directory
/usr/bin/locale: Cannot set LC_ALL to default locale: No such file or directory
Generating locales (this might take a while)...
  en_US.UTF-8... done
  es_ES.UTF-8... done
Generation complete.
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LC_CTYPE = "UTF-8",
    LANG = "C"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LC_CTYPE = "UTF-8",
    LANG = "C"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").

Solution

Execute these export commands and then run dpkg-reconfigure locales again. Now the generation won’t produce any errors.

root@localhost:~# export LANGUAGE=en_US.UTF-8
root@localhost:~# export LANG=en_US.UTF-8
root@localhost:~# export LC_ALL=en_US.UTF-8
root@localhost:~# dpkg-reconfigure locales
Generating locales (this might take a while)...
  en_US.UTF-8... done
  es_ES.UTF-8... done
Generation complete.
root@localhost:~#
root@localhost:~# dpkg-reconfigure locales

Remember to fix this issue BEFORE you run your first apt-get update && apt-get upgrade, so the issue is solved before new packages are installed.