I know I've had changes like this throughout my life, but there are two that I recall quite vividly. The first one was when Kelsey Grammer died years ago. "But he's not dead," you say? That's my point. I vividly recall TV news reports, web articles, and gossip about it for months after it happened. It wasn't until he was cast in X-Men 3 years later that I thought "WTF?? He's supposed to be dead!!"
I do vaguely remember SOMETHING significant with Kelsey Grammer. Another big one was Ringo Starr. Many of us remember him dying of something like cancer. I remember thinking how sad that Paul was the only one left. Then, someone on the forums mentioned him and many of us were like what??! He died. Obviously, someone visited the past of our current timeline and their interactions caused changes. Now, the past we "remember" doesn't match the "new" past. And I agree with you that not everyone's perception of the past is going to match for this very same reason.
Now, think of this. If a person is time traveling, it only involves this own consciousness. His traveling doesn't cause EVERYONE to travel. So, who is to say that the changes he makes don't only affect him? We don't really know.
This phenomenon is illustrated in the story of the man from Taured from 1954. In "his past", his country is Taured. In ours, it's Andorra.
Now, I'm trying to figure out why this example sounds so familiar. I may have read about it before.