Fraudulent *.google.com certificate issued

It's a human problem not a technical one which is why it might seem vague. Clearly a "new" CA showing up in the same area as the old one would come under extra scrutiny. They could check their WebTrust audits and registration and see who audited them and what they found. They could check who are the officers and ownership of the company, how long the company has been around, if it shares office space with the "old" company. They could look at public tax info to see if the organization has been around and has books that make sense. If the company is public they could look at the books themselves (heck for high-value sales private companies have been known to let potential customers look at the books to reassure them).

Building up the paper trail that a CA needs to be accepted by the browsers does require effort and time but you are right in that I have not worked close enough to the CA/browser relationship to know exactly what is required to register with MS, Mozilla, Apple, Opera, Oracle, Google, RIM, and other vendors.