I am trying to find an angle of change on a device that rotates back and forth (picture a door rotating back and forth from a door frame), however it does not move on a fixed axis. To find the angle of change, I am using these compass sensors.
One sensor (reference) is fixed and the other is on the end of the moving device. The theory is that if the sensors starting positions are oriented in the same direction, the initial difference should be zero and subtracting the moving sensor heading from the fixed sensor heading should give an accurate difference when the device moves. This works fairly well in a fixed location, but I move the entire system to another location (the sensor orientations in relation to each other are not changed) the difference between the sensors changes anywhere from 5-15 degrees.
I have tested this indoors and outdoors and calibrated many times, and still have this issue. Do I have some fundamental theory about magnetometers wrong? I don't necessarily care about getting an accurate heading, but the difference between my two sensors I assume should always be the same no matter where they are if they are oriented the same way.
Any current carrying wires, magnetic fields or iron-containing materials near the magnetometer will introduce local distortions in the Earth's magnetic field, and easily cause orientation errors of 5-15 degrees (and much worse).
After calibration, does your compass work perfectly outdoors (that is, does it track orientation changes to +/- 1 degree, about a full circle)?
It does for the most part get accurate readings, but not within 1 degree. However, the accuracy of the heading really doesn't matter to me, I'm more concerned with the relative difference between my two sensors.
For example, I have written a program that takes my initial difference and sets it equal to zero and then measures the angle difference as the device moves with respect to that. My headings don't really matter, it's the difference between them that I want. As long as the initial difference stays the same, the program works perfectly. However, If the setup is moved even just 2 ft away in the same area (without changing the sensor relative orientations), the difference changes. I understand that the headings will change when the setup is moved to a different location, but if the sensors orientations relative to each other have not changed, why would the difference between their headings change drastically?
I hope that made some sense, these sensors have been incredibly frustrating. 
why would the difference between their headings change drastically?
Have you looked for the presence of iron-containing materials, magnets or current-carrying wires?
Walk around the area, holding the compass in the same orientation relative to the Earth's North pole. If the readings change significantly, the answer to the above question is yes.
I know I definitely have a lot of interference inside, but I just assumed that wouldn't be a big issue outdoors.
I read that certain sensor readings are effected by wire length, and my sensors have fairly long wires connecting them to the board (about 2 - 3 ft), could this be contributing to the problem?
Current carrying wires create magnetic fields. However, I doubt that 2-3 ft of wire carrying just the sensor current would be a problem.
You try can twisting just the power leads tightly together (not the signal leads), which strongly reduces magnetic fields. Adjacent conductors carrying current in opposite directions cancel each other's contribution.
In your opinion, would a gyro+accelerometer sensor be a better fit for the situation I described?
No, because MEMS gyros measure the rate of rotation, not the rotation angle itself.
If local magnetic distortions are indeed interfering with your compass measurements, the only recourse is to calibrate the compass in place, to hopefully take those local distortions into account.