I worked this out for myself, but I wanted to post it as a question because I couldn't find anything when I was searching. Lots of people talk about the "menu access key" problem, but this is actually unrelated.
I've enabled a bunch of no-prefix shortcuts is tmux (like Alt-c for new window, Alt-n for next), which has made my life so much better. The problem was, my shortcuts didn't always work. Maybe every 5-10 presses, something would just swallow the keypress, and I'd have to do it again. Sometimes it would send input to the terminal, which was even worse.
The problem turned out to be Unity. The bare Alt key is the default "Key to show the HUD", and somehow that binding was occasionally mucking with Alt chords in my terminal. Here's how to unset it:
# install ccsm if you don't have it sudo apt-get install compizconfig-settings-manager # open the compiz settings ccsm
In the window that comes up, find the "Unity" plugin under the "Desktop" section. The very first item in there is "Key to show the HUD", which defaults to "<Alt>". Click on the "<Alt>" button and uncheck the "Enabled" box. Done!