Resolvi por conta própria, depois de ter uma idéia provocada por @Mrokii.
No menu Keyboard Shortcuts , fui para a seção Custom Shortcuts e adicionei um novo atalho atribuindo Ctrl+Alt+T ao comando gnome-terminal . Isso funciona!
Deve haver algo errado com minhas configurações de terminal padrão ... Mas não vou me preocupar com isso, desde que meu atalho funcione.