Debian locales Perl error

With several installed Debian servers I got the following error when installing a package via apt-get or dpkg:

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

The error here is the part where you see "(unset)". So if this set, the problem should be solved.
So you can try to set the "LC_ALL" variable via: dpkg-reconfigure locales
However this didn't solve it for my servers.

In this part I didn't want the NL language installed, but it did anyway because I choose the NL as the prefered location.
Now I want the en_US.UTF-8 language on my whole system.
If you want to fix this you can run:

export LANGUAGE=en_US.UTF-8
export LANG=en_US.UTF-8
export LC_ALL=en_US.UTF-8
locale-gen en_US.UTF-8
dpkg-reconfigure locales

And this works. The "LC_ALL" variable is set and the error disapears. But wait... What if we logout and login again. Then the problem returns (because you set the variables for your session only).
So you need to set the "LC_ALL" variable in your system environment settings:

root@server:~# echo "LC_ALL=en_US.UTF-8" >> /etc/environment

Now you should have this:

root@server:~# cat /etc/environment
LC_ALL=en_US.UTF-8

Problem solved 8-)