man: can't set the locale; make sure $LC_* and $LANG are correct

I keep getting this error:
man: can't set the locale; make sure $LC_* and $LANG are correct

I tried locale-gen and many other things, without success.
The only thing that fixed it is: export LC_ALL=en_US.UTF-8 (which of course can be added in .profile to be permanent)