How to fix set locale error?

Usually, I thought dpkg-reconfigure locales can fix the locale error but I faced with the case it can't be recovered with dpkg-reconfigure locales like ロケールを変更する - Shammerism. Here is a log.

root@Server1:~# 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 = "C"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
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)...
  ja_JP.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").
root@Server1:~# 

If dpkg-reconfigure can't recover locale errors, editing /etc/environment and logout can fix this issue. http://mrilhan.com/247/lc_ctype-lc_all-problems-on-a-fresh-install-of-debian-squeeze/ tells this way. Here is a copy of it's procedure.

1. echo LANG=ja_JP >> /etc/environment
2. echo LC_CTYPE=ja_JP.UTF-8 >> /etc/environment
3. logout and login
4. perl -v(this is an easy verification way)

perl -v doesn't output locale errors, it is fine.