I had the same experience. I downloaded and installed a Flash grabber program from Softonic and realized almost immediately from the sluggish behavior of my machine that I had picked up rogue software along with the program. I immediately uninstalled the program and rebooted, but then I started getting the relentless CE_UmbrellaCert warning pop-up window. As you mention, it makes the machine unusable. I rolled back as you did which got rid of the warning window, but I was still suspicious about what had been causing the relentless certificate warning pop-up even though the offending program had been uninstalled.
I installed Malware Bytes Free (made sure I updated it with its latest definitions) and did a full system scan. It found 3 PUP (Probably Unwanted Program) items that I didn't have before.
Registry Keys Detected: 1
HKCU\Software\Softonic\Universal Downloader (PUP.Optional.Softonic.A) -> No action taken
Folders Detected: 1
C:\Documents and Settings\Margaret\Application Data\ContentExplorer (PUP.Optional.ContentExplorer.A) -> No action taken.
Files Detected: 1
C:\Documents and Settings\Margaret\Application Data\ContentExplorer\RootCert.cer (PUP.Optional.ContentExplorer.A) -> No action taken.
I checked the little boxes to get rid of the items, but first I had a look at the "RootCert.cer" file. It was a "DO_NOT_TRUST_FiddlerRoot" certificate.
I wish I could help you directly identify which program was causing your CE_UmbrellaCert warning, but I suspect that you must have intentionally or unintentionally installed something or upgraded something just prior to your getting the warning pop-ups that altered your system. That would be the culprit program, add-on or update that you're trying to identify.
Have you tried running a full system scan with the latest updated version of Malware Bytes? It would be interesting to see if you find a registry item and/or a RootCert.cer file on your system as I did.
"CE_UmbrellaCert"
on the net returned very few results, and not much information at all. Should the problem reappear, consider using Process Monitor for further insight.