Eu resolvo esse problema instalando o xterm a partir do software e executando /usr/bin/gnome-terminal . Isso me deu um erro que eu não tinha visto antes, e que minha instalação em python não era a esperada. Eu consertei a instalação do python e tudo funciona novamente.
O problema do python era que eu estava tentando usar um gerenciador de versões do python, mas o gnome-terminal estava procurando pelo binário python3 em /usr/bin . Eu desativei esse binário renomeando-o para old_python3 . Eu o renomei novamente para python3 e tudo funcionou.