Why is my instrumentation amplifier's gain non-linear?
Most likely a common-mode voltage violation.  See Figure 15 of the datasheet.  Unfortunately it does not give you the limits for a single power supply, but shows you that common-mode and output voltage limits go hand in hand.  

Actions that may solve your problem:


Use dual power supply.
Lift inputs above ground.
Use a lower gain setting.


EDIT:

As pointed out by Dave Tweed, the datasheet does have information on common-mode and output voltage ranges for single supply.  See Figure 13 on page 10 of the datasheet (your case is the blue triangular area).  Your common-mode input is practically ground, so as soon as your output exceeds about 0.7 V, the limit is exceeded, and your device will not behave as specified.  This will happen even if you change Vref to 2.5 V: the output limit will be 3.2 V for a common-mode input voltage of ground to become invalid.