The (partial) solution to this problem is very well known and is already implemented by SSH and several other packages that rely on public cryptography: 1) When user visits a new site, the certificate is presented to the user for inspection. 2) On subsequent visits, the site's certificate is compared to the one stored in the browser cache. If they are the same, then the connection is made silently. If there is difference, then the new cert is presented to the user for inspection.

The only problem is that this would kill user experience for 99% of the users who don't care about security in the first place. Thus, browsers need to do some clever UI tricks (e.g. color the thingy in url bar in a different color, etc.) to indicate potential problem to the user yet make it less intrusive.

The bottom line is that the fault is not on the SSL/x509. This infrastructure is not perfect but there is nothing better even in the design. The fault is on the browser developers who are not trying to protect users.