Instrumentation amps and op amps never output a full scale, 0 to VCC range. For the INA125P specifically it's a minimum of .4V to VCC - 0.9V, typical.
You have to be aware that the load cell is never going to show a perfect, 0V differential output between its signal wires; you're always going to see a little offset. If you set the gain of the InAmp too high you're going to be magnifying that offset excessively. From experience I can say that the resistance setting the gain needs to be precise to 2 ohms or less. The Instructable's suggestion of using a 10 ohm resistor is naive -- you need to fiddle with that value to see what works best for your load cell. Ideally you'd use a 50 ohm, multiturn pot for this; you would start at 50 ohms and slowly decrease the resistance right until the point you see the output start to change -- that's your ideal gain setting.