When I change the localization settings on my MacBook Pro, ssh locale/encoding behaves differently from when I was using standard settings. That is using region=United States works, region=Norway not so much.. I noticed the problem when I was unable to type norwegian characters into the remote shell.
The fix is simple. (Thanks goes to this guy)
Comment out SendEnv LANG LC_* in /etc/ssh_config.