Ubuntu 12.04 strange locale behavior

Question

I'm running Ubuntu 12.04 with Vagrant. And I'm having hard time understanding what's wrong with locales on my system.

When I login to my box via ssh

$ vagrant ssh

and try to run something locale related I see that something's wrong:

$ locale
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
LANG=en_US.UTF-8
LANGUAGE=
LC_CTYPE=UTF-8
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=

or, for example

$ nonexistcmd
Sorry, command-not-found has crashed! Please file a bug report at:
https://bugs.launchpad.net/command-not-found/+filebug
Please include the following information with the report:

command-not-found version: 0.2.44

But when I relogin under the same user with sudo su - vagrant everything becomes fine:

$ locale
LANG=en_US.UTF-8
LANGUAGE=
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=

vagrant@vagrant-ubuntu-precise-64:~$ nonexistcmd
nonexistcmd: command not found

How could it be? What's happening?

Thanks in advance!

Additional info:

$ cat /var/lib/locales/supported.d/local 
en_US.UTF-8 UTF-8

$ cat /etc/default/locale 
LANG="en_US.UTF-8"

Answer 1

I got it.

It wasn't a server-side problem. It was my MacOS SSH client sending some locale related env vars (LANG, LC_*). Thanks to a lifesaving post!