What happens when a root CA has its private key compromised? Then all children in the tree are compromised too? And then all certificates are compromised? What needs to happen then?
A lot of sleepless nights for the CA, their customers, web browser and OS developers, and Slashdot users, that's what.
I don't know if a CA has ever had their private keys compromised, but there have been incidents where their systems were broken into and fraudulent certificates were issued. (There's a difference between a private key actually being taken, and an attacker just being able to feed bogus certificates into the system and get them falsely signed -- though both are quite bad enough.)
In 2011, a reseller for Comodo (one of the largest CAs in existence) was compromised and used to issue several fraudulent certificates for google.com and other major domains. Comodo quickly revoked the certificates and disabled the reseller's account, and as a bonus (since online OCSP and CRL checks can be blocked) web browsers and OSes released updates specifically blacklisting those certs.
Comodo was "encouraged" to be more careful -- indeed, another reseller account was compromised less than two weeks later but the attacker was unable to accomplish anything with it -- but their roots were not revoked and they suffered no major consequences. (The reseller is still around, too.) There was a great deal of handwringing around the Internet about whether this was an appropriate response to a limited breach or whether Comodo had made an unforgivable mistake but received "too big to fail" special treatment.
Later in 2011 (bad year), a CA called DigiNotar was compromised, and hundreds of fake certificates were issued, for Google and all sorts of other domains (again). When web browser and OS companies were eventually informed, they revoked DigiNotar's roots from their certificate stores -- defanging the fraudulent certs but breaking many (largely Dutch) websites in the process.
DigiNotar avoided informing anyone of the incident for more than a month, and were unable to produce a complete list of fraudulent certs. Mozilla, for one, lost confidence in them, and DigiNotar was bankrupt in weeks.
That's correct. If this happens, then your PKI is doomed and you have to set it up again and roll out all the certificates again.
Actually, then not all the certificates are "compromised" in the sense of key compromise, but you cannot longer trust them, since if someone is in possession of the root private key, this person can issue arbitratrily dated certificates and you can no longer distinguish between real and fake certficates. Consequently, then you are in real trouble.
This is the reason why root private keys should be protected very very good. Therefore, generally, you use a hardware security module (HSM) to store the respective private key and keep it offline.
Notice, that the root private key is only needed for signing the next level of intermediate certificates in the tree and you need the key only for this purpose. All the certificates in the lower levels are signed by the direct ancestor in the tree (and there, the root key is not involved). Nevertheless, also the intermediate private keys should be kept in secure storage (such as HSMs). Because, if the private key of some intermediate CA certificate is compromised, then the entire subtree having this intermediate CA as root is compromised.