Certificates are installed with programs such as IE and Firefox which allow you to connect to remote sites (e.g. google, yahoo, banks, stock brokers, etc.) securely.
The reason for their existence is b/c typically you don't know whether the site you are connecting is "really" the site you want to go into. Attackers are do man-in-the-middle attacks for example and masquerade as the site you want to be in and capture your important data - e.g. passwords, login information, financial data, etc.
The certificates are "installed" on your computer - so you know that as "fact".. It is very unrealistic for you to know the "keys" of all the sites on the internet - so you only know some of the keys of "parent" sites (wrt security).
The sites (e.g. Verisign) will assign AND sign new keys (call them certificates) to other companies like microsoft, google, yahoo, banks, etc. that you can use to establish a secure link with them. You can verify the authenticity of those certificates since you have the "keys" of the parent companies (also certificates - called root certificates) installed on your computer already. Since there are only a few such parent companies, it is manageable.
It forms a heirachy of multiple levels..
That was a quick but long write. Hopefully, it was clear
..
If your computer is complaining about certificates, it either means your root cretificate store is corrupted, someone is trying to redirect you and capture important data from you, or even the "time" is incorrect, etc.
In your case, it sounds like just a problem on your system sinc eu said u just installed Service Pack 2.. Please post the exact error msg.