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.
I can update my pull to implement the latest version of the generalized proposal within two weeks. I have not been motivated to do so because of the issues that @maaku raises. If such a pull will be seriously considered I can go ahead.
I don't see the problem with wallet security/backup on top of the generalized case. To get the a AND b OR c case, just use 2-of-2 OR 1-of-1.