The difficulty with any "travelling between measurement outcomes" model is that it implies a direction of travel: in any particular instance, does the influence propagate from measurement A to influence the result at B, or does it propagate from measurement B to influence the result at A? We're hypothesizing a physical effect here, so this direction of travel should be a frame-independent invariant - but it cannot be if the two measurements are spacelike-separated, and that creates the conflict with both relativity and the common-sense notion that causes must precede effects.
The correlation between entangled particles is of a different nature. The change of system state upon measurement is the same no matter which measurement we consider to be first (which suggests that maybe that's not something that we need be considering) so there is no way of identifying one measurement as the source of the influence and the other as the recipient. Indeed, the impossibility of communicating by entanglement follows from the way that the math describing entanglement is explicitly acausal.
So the non-local correlation is spooky, more so because it cannot be explained as I would, for example, explain spooky haunted house phenomena ("Nonsense - that's not some supernatural creature, it's mice in the walls or windows rattling in the wind or something and I haven't figured out what yet") by assuming that there's a causal mechanism that I haven't figured out yet. But the conflict with relativity only appears because we've introduced this assumption of a propagating influence, demanded by our classical intuition but not in the math or in the observational results.