This is a massive bug that happens almost every time I install a new server. It's because I use a non-standard US locale so I always get conflicts. This fixes this issue.

The warning message during the installation of Perl applications will appear as follows:

justin:~$ sudo apt install something
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
	LANGUAGE = (unset),
	LC_ALL = (unset),
	LANG = "en_GB.utf8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").

The first option you have it to fix missing locales by generating them with locale-gen:

justin:~$ sudo locale-gen en_GB.UTF-8
/bin/bash: warning: setlocale: LC_ALL: cannot change locale (en_GB.UTF-8)
Generating locales (this might take a while)...
  en_GB.UTF-8... done
Generation complete.

That's it. You should be OK.

If Fix 1 didn't work, the locale settings can be set (to en_GB.UTF-8 in the example) as follows:

$ sudo dpkg-reconfigure locales

The dpkg-reconfigure locales command will open a dialog under Debian and Ubuntu for selecting the desired locale.