Você pode usar apenas Keyboard Shortcuts , disponível na Pesquisa do Menu Principal.
Apenas Add um novo item ... por exemplo. chamado mate-terminal ... o comando deve ser mate-terminal
Em seguida, clique no novo item (que aparece na parte inferior da lista) .. e digite Control-Alt-t ...
Tudo pronto ...
Se você tiver compiz instalado, também poderá usar as opções Commands , mas o método acima ainda deverá funcionar.