I think the INA125P blows only the signal up but you have in the best case still the 10bit resolution of the Arduino. If you boost with the wrong gain you can not use the full range and you have less than 10bit
It should help to use an external ADC (with integrated op amp). I have used the ADS1231, a 24bit ADC and also the HX711 successful with a load cell. For the HX711 have a look at this break out board Gravity: Arduino Digital Weight Sensor - DFRobot
It is also a good idea to smooth the readings by a running media, see Arduino Playground - RunningMedian but this will not help if the raw value altered +/-1 around.