What is the gain of the INA125 set to?
It sounds like you need a lot more gain in the instrumentation amplifier. If you don't have a resistor \$R_{G}\$ between the pins 8 and 9 of the instrumentation amplifier, your overall gain of the load-cell output will be only 4.
The load cell you have specced has a 1 mV/V output. Since it sounds like you're feeding the load-cell with your 2.5V reference, this means the full-scale output of the load-cell will be 2.5 mV. With the 4X gain in the INA125, that is 10 mV into the ADC input.
With a 10-bit ADC and 2.5V reference, your bit-size is ~0.0024 v/bit (\$\frac{2.5V}{2^{10}}\$), you should expect a change of \$\frac{0.010V}{0.0024V} \$, or approximately ~4 LSBs, and that's for the maximum load the load-cell is rated for.
So... Unless you have something else going on that you have not described, it sounds like you're getting significantly more output then would be expected. I would guess you have some gain in the INA125 that you have not described.
The solution here, of course, is to put a voltmeter on the interconnect between the INA125 and the MCU's ADC. That way, you can measure the real voltage going into the MCU, which will tell you where your error is coming from (MCU's ADC, or the INA).
The ADC that most of hobbyist use for Load cell is ADS1130. This is an 18 bit ADC with internal gain of 64 which transmits the converted bits serially. It would be easy to answer if you had mentioned the model of your microcontroller, because some of the microcontroller has amplifier embedded in it with high resolution bits of adc like Atmega16.
Best Answer
These things happen in checkweighers all the time and the common way around this is for the software to simply ignore the glitch i.e. throw away those readings that look suspicious.
A lot of checkweighers also use an optical device to sync the software up with the position of the "thing" to be weighed thus the software knows when it should be using readings to calculate weight.
This problem is usually due to cantilever resonance as the "thing" initially slides onto the edge of the weigh-part of the conveyor.
I reckon you should show a picture of weight results versus "thing" position as it passes over the weighing section. This will allow further analysis by me and others. I recommend that you have an ADC rate that would take several tens of readings (if not hundreds) as the thing passes through the weigh section.