В моята дистрибуция "locale-gen" не беше инсталиран и се оказа, че всичко, което трябваше да направя, е да задам променливата на средата LC_ALL. Така че следната команда го поправи:
export LC_ALL="en_US.UTF-8"
надявам се, че ще помогне на някой друг...