Terminal.app is actually doing what it's supposed to: shift-TAB sends ESC [ z which Emacs reads as M-[ z. The problem is that the terminal description for xterm-color (the one usually used with Terminal.app and other terminal emulators) is missing the kcbt declaration, so Emacs doesn't know that that's what the key sends.
There are two ways to fix this:
Edit the terminal description:
$ infocmp >xterm-color.ti
$ printf '\tkcbt=\E[Z,\n' >>xterm-color.ti
$ sudo tic xterm-color.ti
Tell Emacs about it directly:
$ echo "(global-set-key "\M-[Z" 'something)" >>~/.emacs
The problem in both cases is that there doesn't seem to be a backwards-tab command to substitute for something. Emacs.app binds backtab to yank; what do you want it to do?
In general, Mac applications that are expecting text input from the keyboard do not handle C-S combinations or C-digit combinations. Programs that work with control-shift combos (like anything running under X11) do so by handling key events as events, not character input. This is how they can differentiate between Tab and Ctrl-i, which both generate the same ASCII character. (You can read in detail how Lion (really Cocoa) handles key events if you really want to know.)
Historically (back in the Teletype days), there were only uppercase letters on the keyboard, and there were no caret (^) or underscore (_) characters on the keyboard (instead there were up-arrow and back-arrow). The shift key worked by toggling the 16's bit and the control key worked by zeroing the 64's bit of the 7-bit ASCII codes the keyboard produced.
What this means is that the control key had no effect for the 32 characters on the keyboard that already had their 64's bit set to zero (most of the non-alphabetic characters, including digits), and since the teletype was purposefully limited to upper-case letters only, the shift key had no effect on most of the alphabetic characters (and where it did have an effect, it produced a special character like @).
Additional weirdness was added in the migration to supporting lower-case text, as the control key combos were all typed without using the shift key but now the letter typed without using the shift key had changed, so the decision was to map control-lower-case to what had been control-upper-case. But then what do you do with control-shift?
For a while the problem was handled by having the control key also zero out the 32's bit, which is what differentiated lower case letters from upper case letters. But eventually ASCII was replaced with Unicode and those kinds of duplicate key assignments were too much of a waste of keyboard space to be allowed to continue, so they got different mappings, and on the standard Mac US keyboard most C-S combos are unassigned.
So what you have run into is the legacy support for keyboard input running back to Teletype days. The characters Terminal (and other OS X apps) do not support are characters you could not type on the Teletype keyboard. As evidence of this, note that C-S-2 (C-@), C-S-6 (C-^), and C-S-- (C-_) all work, because those keys have been re-mapped since the ASR-33, where S-2 was " (and @ was S-P), S-6 was &, and S-- was =, but in general control-shift combos do not produce characters of any kind.
Best Answer
The following worked for me:
Open "System Preferences", select "Keyboard", then "Shortcuts".
From the list of shortcut categories in the left-hand list, select "App Shortcuts".
Add (this is counter-intuitive since you want to disable an existing shortcut) a new shortcut using the "+" button:
Under "Menu Title", enter "Lock Screen" (this should be how the action appears on the "Apple" desktop menu).
Then under Keyboard Shortcut, enter a key combination that you can "sacrifice". You could use something hard to type like Ctrl + Alt + Cmd + Shift + L.
You "save" the new Keyboard Shortcut (which actually overrides the previously invisible Ctrl + Cmd + Q shortcut) by closing the Keyboard preferences window.
Now you should be able to enjoy Ctrl + Cmd + Q's awesome Emacs binding again.