Setting locale failed

I've been getting this annoying warning on a number of servers for months now:

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
	LANGUAGE = (unset),
	LC_ALL = (unset),
	LANG = "en_NZ.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").

I've have tried reconfiguring/reinstalling locale, reconfiguring tzdata and a number of other things but to no avail. Finally I did the following which fixed it:

locale-gen en_NZ.UTF-8