Выполнить sudo dpkg-reconfigure locales в альтернативном эмуляторе терминала и выбрать en_US.UTF-8 UTF-8, выбрать его как локаль по умолчанию. gnome-terminal должен работать.