I had a similar problem and found a solution. The distribution I've got is Linux Mint w/ Cinnamon GUI, which is offered as Debian-based or as Ubuntu-based versions. Mine's the Debian-based version, identified as 201303 presumably for March 2013, at a time when the Ubuntu-based version is named 16 Petra.
Clicking my way through menus starting at the taskbar (or whatever it's called in Cinnamon)...
Preferences -> Cinnamon Settings -> Keyboard
Here I went to put a Terminal shortcut, to use Ctrl-Alt-t for the terminal, but I see it's already there in the list from a fresh installation. Yet Ctrl-Alt-t doesn't do anything when I type it. Odd. So that's a dead end.
Going into the file manager worked. Navigate your directories to here:
and double-click the "keyboard" program in there. You cannot open the program from the command line, you have to be in a graphical file manager. If you were to try opening it from a terminal, you'd first realize the actual name of it is gnome-keyboard.desktop. There's a help page discussing how .desktop files can't be opened via a terminal: http://askubuntu.com/questions/5172/running-a-desktop-file-in-the-terminal
Anyway, once you've double-clicked it and opened it, entering your settings there works. In the left sidebar, click on "Custom Shortcuts", then click on the + sign. In the text field for Name, put Terminal or whatever you want -- the name doesn't matter. In the text field for Command, put x-terminal-emulator. Don't have a period after it, I was just ending my sentence.
Lastly, on the right side of the window is the word Disabled. Do a single click on that word (not just anywhere on the line) and it'll change to New Shortcut, at which point you can hold down the Ctrl and Alt keys and hit the letter t, to input the Ctrl-Alt-t shortcut. If nothing seems to happen, be advised that accidentally doing a double-click instead of a single click toggles it so quickly (from Disabled to New Shortcut back to Disabled), you'd be forgiven for thinking your input was ignored.
Now try using your shortcut. For me it goes into effect before even quitting the program.