No Debian 8, as preferências do gnome-terminal mostram o atalho esperado (para mim) e testam os atalhos.
No entanto, você pode ter caído na armadilha lançada pelo mantenedor do terminador, que sequestrou o x-xterminal-emulator prioridade um par de anos atrás. Eu não observei isso no Ubuntu 14.04, mas ele está presente no Debian 8. Se você está usando o "terminal", esse incômodo pode ser contornado usando
sudo update-alternatives --config x-terminal-emulator
Por que vale a pena, é isso que eu uso:
$ sudo update-alternatives --config x-terminal-emulator
[sudo] password for tom:
There are 20 choices for the alternative x-terminal-emulator (providing /usr/bin/x-terminal-emulator).
Selection Path Priority Status
------------------------------------------------------------
* 0 /usr/bin/xterm-dev 60 auto mode
1 /usr/bin/gnome-terminal.wrapper 40 manual mode
2 /usr/bin/koi8rxterm 20 manual mode
3 /usr/bin/konsole 40 manual mode
4 /usr/bin/kterm 21 manual mode
5 /usr/bin/lilyterm 20 manual mode
6 /usr/bin/lxterm 30 manual mode
7 /usr/bin/lxterminal 40 manual mode
8 /usr/bin/mate-terminal.wrapper 30 manual mode
9 /usr/bin/mlterm 20 manual mode
10 /usr/bin/mrxvt-full 10 manual mode
11 /usr/bin/pterm 20 manual mode
12 /usr/bin/roxterm 50 manual mode
13 /usr/bin/stterm 15 manual mode
14 /usr/bin/terminator 50 manual mode
15 /usr/bin/urxvt 20 manual mode
16 /usr/bin/uxterm 20 manual mode
17 /usr/bin/vala-terminal 50 manual mode
18 /usr/bin/xfce4-terminal.wrapper 40 manual mode
19 /usr/bin/xterm 20 manual mode
20 /usr/bin/xterm-dev 60 manual mode
Press enter to keep the current choice[*], or type selection number:
Da mesma forma, o vala-terminal faz isso. Ambos são menos funcionais, por exemplo, que o gnome-terminal.