OK, here's some followup. I have 2 Macbook Pro's, my wife's is a mid-2008 and it works perfectly after the upgrade. Mine is an early 2011 model and is experiencing the same issues as everyone else, as described in my earlier post. After trying all suggestions (without result) and even re-installing the OS and upgrading with the Combo Updater, I still had the certificate error. Since this prevents me from working, I ended up doing a full restore from Time Machine to 10.7.3 and all is well.
I am not behind a corporate firewall, and my wife's machine works fine when on the same network. I did have some ports forwarded to my MBP, which shouldn't have made any difference, but I disabled them this morning, reupgraded to 10.7.4 and had the same issue again. I have just finished restoring 10.7.3. yet again from Time Machine.
I hope this helps move the enquiry forward; I don't believe that the issue lies with proxies or corporate firewalls. Since my working machine is a Core 2 Duo Penryn and the problem machine is an i7 Sandy Bridge, I'm wondering if the problem may lie in the different architectures?