The same happens even if the stage is not powered. Just the connection to the power outlet, even when it is turned off causes the same (hence my suspicion of the grounds).
As far as my practical problem goes, I simply connected the signal through a voltage divider thus mapping the [-7,7] to [0,5] (See attached diagram). So other than losing some resolution, I can perform my measurement.
You can improve your measurements by bringing the voltage down to 0-1V, and using the internal analog reference. More stable than using Vcc as reference.
The load cell amplifier outputs both negative and positive voltages (something like -7 to 7V). When I connected to the Arduino, I flipped the signal and ground, so measuring the ground in an analog input and connecting the signal to the ground. It worked fine before connecting the additional stage device.