I faced next error when I start some console applications, for example Asbru: perl: warning: Setting locale failed, it was really annoying but I found how to fix it..

In my case full error looked like

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
	LANGUAGE = (unset),
	LC_ALL = (unset),
	LC_TIME = "en_US.UTF-8",
	LC_MONETARY = "en_US.UTF-8",
	LC_ADDRESS = "en_US.UTF-8",
	LC_TELEPHONE = "en_US.UTF-8",
	LC_NAME = "en_US.UTF-8",
	LC_MEASUREMENT = "en_US.UTF-8",
	LC_IDENTIFICATION = "en_US.UTF-8",
	LC_NUMERIC = "en_US.UTF-8",
	LC_PAPER = "en_US.UTF-8",
	LANG = "C"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").

Previously I already faced with something similar and fixed it by regenerating locales with the next command

$ sudo dpkg-reconfigure locales

But this time re-configuration didn’t help.

As you can see in the error LANGUAGE and LC_ALL were not set and it was the main reason of the problem. I resolved this by adding this settings to /etc/environment file

$ sudo nano /etc/environment
...
LC_ALL=en_US.UTF-8
LANG=en_US.UTF-8

After this the problem was resolved.