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.