You can fix the error by installing locales-all, on Debian by doing:
apt-get install locales-all
And then adding this to your GemFile:
if RUBY_VERSION =~ /1.9/ Encoding.default_external = Encoding::UTF_8
Encoding.default_internal = Encoding::UTF_8
You might also want to try to export the variables:
export LANG="en_US.UTF-8" export LC_ALL="en_US.UTF-8"
Either one of the 2 solutions will solve the issue.