I noticed the exact same issue when logging onto servers running Red Hat from an OSX Lion machine.
Try adding or editing the ~/.profile file for it to correctly export your locale settings upon initiating a new session.
export LC_ALL=en_US.UTF-8
export LANG=en_US.UTF-8
These two lines added to the file should suffice to set the locale [replace en_US for your desired locale, and check beforehand that it is indeed installed on your system (locale -a)].
After that, you can start a new session and check using locale:
$ locale
The following should be the output:
LANG="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_CTYPE="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_ALL="en_US.UTF-8"
If this does not work, here is a piece [link] discussing how to replace the outdated bash version in OSX with a newer one from MacPorts and set that as your default one.