Every experimental confirmation of Bell's Theorem shows the transmission of information at a speed faster than light. If a particle that is not in an eigenstate along a particular axis is measured along that axis, this automatically collapses the wavefunction for any particle that is entangled with it. For instance, an electron positron pair can be in a superposition of two states, one where the electron has positive z spin and the positron has negative z spin, and one where the electron has negative z spin and the positron has positive z spin. There is nothing special about the z axis: The same wave function can be expressed similarly with regards to the x axis. As soon as a measurement is taken along one axis, a measurement along that axis by another observer must show the same result. A measurement taken along another axis will show random results because of the Heisenberg Uncertainty Principle.
Here is a good place to start your study of the matter, though there are a slew of other experiments which I linked earlier in the post: http://www.nature.com/news/2008/080813/full/news.2008.1038.html
Note: The experimental apparatus I described in the original post is off by a bit, I realized, the measurements need to be taken in a bit more complex manner, using 45 degree angles and such. I linked a list to the experiments done to show the instantenous collapse of the wave function earlier in the thread, you can read about the methods researchers have used in those. But all point to the fact that a measurement can collapse a wave function simultaneously in two far away locations, and this does not jive with special relativity's disproof of the concept of simultaneity.
OK, I think I have a more accurate version of the paradox that doesn't require fancy 45 degree measurements. So, a set of electrons and a corresponding set of entangled positrons are each put on opposing ends of the spaceship. These are in spin eigenstates along the x axis such that the electrons will read a positive spin and the positrons will read a negative spin. One machine measures the spin of its set along the x axis, and the other machine on the other side of the spaceship measures the spin of its set along the y axis. According to some observers, the y spin will be measured first, but according to other observers, the x spin will be measured first. Will the x spin read the definite measurements that were known "before" the y spin was measured, or will it read random measurements? It seems like this points to preferred frames of reference. But even preferred frames of reference can't be a solution, since a ship going in the other direction could be making corresponding measurements, with some paired electrons and positrons on different ships and some on the same ship.
Immortal and IM, it seems to me like, whether either counterfactual definiteness, localism, counterfactual definiteness/localism, or superdeterminism is true, it can't explain why one of the measurements arbitrarily takes precedent over the other. I guess the paradox leads me toward a belief in superdeterminism, but this still doesn't explain the specifics of why the system acts as if it was measured by one of the observers first in a seemingly arbitrary fashion. I guess it might be some sort of inherent randomness of the Heisenber variety. Of course, to be technical, Heisenberg was only half right according to superdeterminism. Heisenberg said that the future outcome of a system can be such that it is not determined yet, and the measurement will be completely random. Superdeterminism says that the future outcome of a system cannot be such that it is not determined yet, but the measurement cannot be predicted.
If the correctness of either observer's point of view is arbitrarily determined, it seems like Heisenberg's Uncertainty Principle and the more modern version, Ozawa's Inequality (see here: http://www.scientificamerican.com/article.cfm?id=heisenbergs-uncertainty-principle-is-not-dead), are both proven wrong by this paradox. Say both sets of particles are in spin eigenstates along the x axis. One observer then sees one of the sets being measured along the x axis and displaying its eigenstate. He then sees the other set of particles being measured along the y axis and showing random measurements. But another observer sees the measurement along the y axis taking place before the measurement along the x axis: This violates Ozawa's Inequality (and Heisenberg's Uncertainty Principle).