Relativity does not allow immediately fast information transmit and usually there is not much point in speculating about it, but regarding Andromeda paradox and its metaphysical grounds I find this somewhat benefical.
Suppose we had some way to transmit information immediately fast, perhaps by some quantum or other currently unknown effect. Observer A walks the street towards Andromeda and, in a sense, lives at the same time with Andromeda future (say, Andromeda time +1). Observer B walks the street away from Andromeda lives at the same time with Andromeda past (Andromeda time -1).
Now, as infinitely fast information tranmit is allowed, A could get information from Andromeda future, pass it to B (remember they are at the same place and time at the street) and B could transmit this information to Andromeda past, which is simultaneous with his own time. So the Andromedans could receive information from their future and, if they wish, act accordingly to prevent this predestined future.
Moreover, in observer A's frame the event "A and B meet" is simultaneous with Andromeda future. In observer B's frame, the event when A and B meet is simultaneous with Andromeda past. But from Andromedans own frame, neither one is correct, but the event when A and B meet happens at other time (Andromeda time 0). So from Andromedans point of view, no information from future to past cannot be transmitted by routing it through A and B back to Andromeda.
So my point is this. There is no logical obstacle for infinitely fast information transfer, maybe we just don't know of any such method (I don't believe such method exists, but we cannot rule it out for sure). If the relative simultaneity was real in the most concrete "really is" sense, this combined with infinitely fast information transfer would easily create impossible situations. Therefore, I personally believe that relative simultaneity is just a calculation and not physically real in the concrete sense.
Sorry about all the metaphysics.