Решение:
Через UI:
Settings::Region & Language::Login Screen -> явным образом выбираем English (United States) без ISO-8859-1 -> Reboot -> Terminal работает.
Нужно переключить
на English (United States) без ISO-8859-1
Тогда после перезагрузки терминал будет запускаться.
Консоль
sudo locale-gen
sudo localectl set-locale LANG=en_US.utf8
reboot system или sudo systemctl restart gdm или sudo service gdm restart