I was getting the same issue in Mac OS X Snow Leopard. It seems to be an issue with Terminal.app.
Please add the following to your $HOME/.bash_profile
export LC_ALL=en_US.UTF-8
export LANG=en_US.UTF-8
Do
source $HOME/.bash_profile
and try. This will solve the issue.