After much fruitful discussion and evolution, this proposal is now a series of "Bitcoin Improvement Proposals" -- see BIP 11, 12 and 13: https://en.bitcoin.it/wiki/Bitcoin_Improvement_Proposals
Sincere thanks to everybody who contributed improvements, ideas and code.
A combination of the previous solution and the DUP NOTIF ... ENDIF 1SUB would work. The advantage of the previous solution is efficiently representing things like 2-of-4. With @gavinandresen's current proposal it would take 12 clauses. The advantage of the current proposal's DUP NOTIF is that only one branch is evaluated.
script.cpp already optimizes the sig = 0 case. If CPU becomes an issue, an extension of the current anti-DOS mechanism could be implemented where a component of the tx fee is proportional to the number of non-0 sigs in the scriptSig.