Steve,
I would like to quote 'PKIX Roadmap- March 10, 2000' [<draft-ietf-pkix-roadmap-05.txt>], part 3.5.6.2. Key Compromise
In the case of a key compromise, the transition will not be "graceful" in that there will be an unplanned switch of PKCs and keys; users will not have known in advance what was about to happen. Still, the PKI must support the ability to declare that the previous PKC is now invalid and shall not be used, and to announce the validity and availability of the new PKC.
Note: compromise of a private key associated with a Root CA is catastrophic for users relying on that Root CA. If a Root CA's private key is compromised, that CA's PKC must be revoked and all PKCs subordinate to it must also be revoked. Until such time as the Root CA has been issued a new PKC and the Root CA issues PKCs to users relying upon it, users relying on that Root CA are cut off from the rest of the system, as there is no way to develop a valid certification path back to a trusted node.
Further, users will likely have to be notified by out-of-band mechanisms about the change in CA keys. [...]
To avoid these out-of-band mechanisms IMO multiply-signed CRLs or OCSP responses are necessary.