By "the cert message/cert issue" I take it that you mean the warning that appears when browser puts up the message about an insecure connection.   This most often happens when a web server uses a self-signed encryption certificate or the client side doesn't have a trust in the presented certificate's authority ( e.g. a company has in internal Certificate Authority that is not recognized "world wide" as say GeoTrust is ).

If either is the case that tells me that 9/10 have accepted the situation permanently whilst the remaining 1/10 have not.  Certificates aren't part of browser's cache so clearing does nothing.

To check whether you have received a trusted (or proper) certificate from the web site, click on the lock icon in front of the URL (in both Firefox and Chrome) and see more information about the SSL connection.

If the 10% happens to be Chrome and you happen to use a Symantec issued certificate, then you have probably got caught in the fight between Google and Symantec. Just search "chrome symantec certificate" and you will see why.