Galera, é só clicar no menu do Mate, digitar "atalhos" ou "key", e clicar em "Atalhos de Teclado" (não tenho certeza se é esse nome, no meu aqui está em francês), ahh, isso no Linux Mint, de qualquer maneira esse programa pode ser encontrado no menu Preferências, daí ao abrir a janela procure na seção de escritório a entrada Lançar um Terminal ou algo assim, dê um clique e aperte Ctrl+Alt+T ao mesmo tempo, pronto, o atalho do Terminal está criado. Não sei porque isso não vem pronto na instalação.
E se digitar Terminal, ele aparece no menu do Mate (naquele menu customizado do Linux Mint).
Qual versão do Mate estamos falando, a propósito? 1.2, 1.4 ou 1.6?