The separate space and time interval measurements between two events can vary among observers, but they will all measure the same spacetime interval, which in turn determines whether light is "fast enough".
To expand on that a bit, this shortest path is known as a geodesic and one of the more important axioms of general relativity is that all laws of physics are preserved locally when traveling along a geodesic. In particular all such observers should measure the same speed of light, since it's a simple property of electrodynamics. Interestingly they won't measure the same CMB, showing that the local part is important.
If so, is that why stuff like QM has trouble, where something like entangled things at a distance might be hard to express locally, or is it actually easy to transform spooky stuff into a local statement and QM issues are something else entirely?
The obstacle to combining general relativity and quantum mechanics is, in short, that general relativity is a classical theory of physics (e.g. exact positions, energy, momentum and all that), whereas quantum mechanics expands classical mechanics to get quantum mechanical laws of physics. Now for whatever reason the techniques we used to turn electromagnetism etc. quantum mechanical fail to work on the (classical) theory of general relativity.
And IMHO that's about as far as we've gotten, a lot of work's gone into it but it's honestly hard to tell if we've gotten a better grasp on why general relativity refuses to 'quantize'. Personally I blame the fact that the mathematical foundations of quantum mechanics aren't strong enough to support a quantum mechanical description of geometry itself, but I may not be the most qualified person to judge this.
If I measure the temporal (dt) and spatial (dx) distance between two events A and B, then I can calculate what another observer would measure (dt' and dx') using the so-called Lorentz transformation, provided that I know his velocity relatively to me (v). The Lorentz transformation is a linear operator, written down as a matrix.
Now, the spacetime interval (ds) between A and B, is computed with the formula ds^2 = dx^2 - c^2 dt^2. The interesting property here is that the Lorentz transformation leaves ds^2 unchanged, i.e. dx^2 - c^2 dt^2 = dx'^2 - c^2 dt'^2. So, it also does not change the sign of ds^2, which determines whether light is fast enough to travel a distance dx within time dt.
The animation in the Wikipedia link by alephu5 shows the Lorentz transformation in action for a smoothly varying value of relative velocity. The events A B C are all separated by positive ('spacelike', light not fast enough) intervals, which graphically means that the line connecting them has a slope of less than 45 degrees in that graph, and the Lorentz transformation can tilt that line both ways and change the ordering of the events in the t axis. If two of these events on that graph were separated by a negative ('timelike') interval, the line connecting them would have a slope larger than 45 degrees and the Lorentz transformation could not alter their relative ordering in the t axis, meaning that all observers would agree on the ordering.