I've tried this explanation before, I'm never sure how well it's received, but I'll try it again.
Suppose you have two cars, with odometers. Both odometers are "synchronized" at the start of the trip, so they both read the same. Then one car takes a straight line path from it's starting location (say Springfield, Ill), to it's ending location (say, Washington DC). The other car doesn't go in a straight line, it goes from Springfield to Atlanta to Washington.
You don't even expect the cars to have the same odometer readings when they both arrive at Washington DC. But you expect that the car that drove in the straight line path has the lowest reading.
The principle behind the odometer reading being a minimum for one car is that "the shortest distance between two points is a straight line". A corollary is that non-straight line paths are longer.
The situation in relativity is somewhat similar, but it turns out that the straight-line path is the longest (proper) time, rather than the shortest. Why this is is interesting, but a little too technical for the point I'm trying to make.
The point I'm making is that the very idea that the two clocks, or cars, should have the same reading on their instruments, their times, or their odometers, is not a logical necessity. The idea that clocks "should" have the same reading comes from the notion of absolute time, usually. This would be the only thing I needed to say, if everyone who read this post knew what "absolute time" actually meant. But they most likely don't (or they would have figured this all out for themselves, ages ago), so I'm going to try the above example to explain.
It's possible to go into a whole lot more detail about the geometry, and at some point it even becomes a good idea. What I'm advocating is to start out with the idea that two clocks don't have to read the same time if they take different paths through space-time. And that there is something special about straight-line motion, which in the case of cars gives the shortest reading on their odometers when they re-unite, and in the case of clocks, gives the longest reading on the clock.
To try and explain to the people who "don't get" where the confusion is, I'll suggest the following model. The people who are confused believe in absolute time, and never thought about time in any other way. They then try to treat acceleration as a physical effect that modifies an underlying absolute time. And they note that this approach just doesn't work. But the idea of throwing out "absolute time" seems too radical to them, it's even hard to talk about it because they'd have to realize an alternative to absolute time even existed before they could think about it. And the idea that it might not apply hasn't occurred to them, and the words pointing out that it doesn't apply don't make any sense, because they don't have the conceptual background to appreciate them.
Now, I can't guarantee that my general model of "why people don't get it" works, but I think it's a good working hypothesis in 90+ percent of the cases.