The recent problem with Android's SecureRandom PRNG once again shows that using (EC)DSA can go horribly wrong if the signature nonce is ever reused.
There is an elliptic curve signature scheme that doesn't share this property: Ed25519.
Is there a mechanism in the Bitcoin protocol to allow transition to a new address/signature format? Would there have to be a new opcode, or does OP_CHECKSIG already support different key types?
What would happen to clients that don't support a new key format, but receive transactions from such a new address/key? Would SPV clients trust a transaction that they can't verify themselves, or reject the block containing it as invalid?
In any case, the new format can only be used once (nearly) all clients support it, but could this be implemented at some point, and enabled some time later?