How to fix warning: setlocale: LC_CTYPE: cannot change locale (UTF-8)

I recently encountered a problem when logging through SSH in to certain servers that I use for work when using my new Macbook Pro (running Lion 10.7.3).

So right after the login was completed I was getting the following message:

warning: setlocale: LC_CTYPE: cannot change locale (UTF-8)

It only happened on certain servers, for […]