"My question to you: how do you train Joe Public to differentiate between: 'This cert has changed!' (you are now being MITMed) and 'This cert has changed!' (the server operator changed their cert)?"
You can't. I know all about how TLS works, but I'd have no idea how to tell whether a cert is actually legitimate. (Look at details, try to find the fingerprints, Google them . . . ?) So you make a best guess. Browsers currently guess that any cert change is due to MITM, and thus throw up scary warning messages and make it difficult to continue. But in fact, as a paper by Microsoft Research observes:
Ironically, one place a user will almost certainly never see a certificate error is on a phishing or malware hosting site. That is, using certificates is almost unknown among the reported phishing sites in PhishTank . The rare cases that employ certificates use valid ones. The same is true of sites that host malicious content. Attackers wisely calculate that it is far better to go without a certificate than risk the warning. In fact, as far as we can determine, there is no evidence of a single user being saved from harm by a certificate error, anywhere, ever.
Thus, to a good approximation, 100% of certificate errors are false positives. Most users will come across certificate errors occasionally. Almost without exception they are the result of legitimate sites that have name mismatches, expired or self-signed certificates.
So if you're going to make an informed guess on the user's behalf, you should guess that the cert is self-signed or mismanaged and not bother the user about it.
Of course, this logic taken on its face would say you should just get rid of TLS entirely, which is wrong. The reason MITM attacks with self-signed certs don't occur is *because* of the warning messages. But the drastic overreaction here by browsers just erodes users' confidence in browser warnings. They need to present the issue more realistically and honestly, keeping in mind that most cert errors are actually innocuous.
(Chrome is particularly egregious here. I've seen it flat-out refuse to let me continue because it thought a cert was expired or revoked or something, but it was just some stupid Microsoft feedback site that I wasn't submitting anything secret to at all, so if it was a MITM I just didn't care. And it makes flat-out wrong claims like "This is probably not the site you are looking for!" Firefox is wordy and tedious, but at least it doesn't outright lie to you. Still, the severity of the warning message even on pages that you can easily guess are legitimate, like <https://amazon.com>, is really unwarranted.)
I think a lot of this debate can be solved by STS. Once all sites that really need TLS are using STS with long expiration times, and browsers come with a prepackaged list of such sites that they update regularly like their lists of malware sites, the UI for non-STS TLS should be relaxed considerably. STS is probably how TLS should have worked to begin with.
Also, serving certs through DNSSEC gives us a chance to make them easier to deploy, and moots the question of self-signing. So I think we can improve the situation a lot here. But browsers' current UI for cert errors still is not at all reasonable.