Descobri que excluir (ou mover no meu caso) a configuração do terminal do gnome localizada em ~/.gconf/apps/gnome-terminal/profiles/Default/%gconf.xml
e reinicializar faz com que o menu reapareça. Eu postei minha configuração aqui para quem estiver interessado (a linha 6 comentada foi a causa do problema).
Não tenho certeza de como consegui a configuração no conjunto da linha 6. Olhando para a caixa de diálogo de configurações do terminal do gnome, não há nada que eu veja que pareça causar esse comportamento.
Editar
Encontrou a configuração. Eu não tenho certeza de como eu perdi antes, ou porque eu cliquei em primeiro lugar. Não sei como esse "recurso" poderia ser bom, já que você não pode voltar às configurações para defini-lo de volta.