Решение нашлось:

sudo apt-get remove rar
sudo apt-get remove unrar
sudo apt-get install unrar
после чего файлролер заработал с кириллицей

PS: Но unrar не поддерживает создание rar архивов
PSS: Но есть еще один вариант:
Поставить оригинальный rar из исходников с официального сайта
Распаковать сорцы и запустить sudo make install