Sorry to revive this. I've found exactly the same problem, and I don't have that last variable mentioned by reinob in my ssh_config, but there is a SendEnv LANG LC_*. Commenting it out didn't work.

The messages just seem to warn about a problem setting up locale, but I haven't seen any trouble with it. Is this just annoying, as the thread title says? =P