Having such high resistances is a problem for the arduino.
When you initiate an a/d measurement, the arduino sucks in a bit of current and charges a capacitor and then tries to match the voltage on the capacitor. The problem is, when this current is sucked in, the effect of that current itself alters the voltage at the "voltage divider" point between your actuals sensor and the resistor which forms a voltage divider in combination with it.
If you have the sensor and the resistor connected in series between Vcc and ground, then a current of a couple of microamps flows through it, and the voltage of the mid-point is determined by the ratio of the two resistances. But if the a/d input of the arduino is also sucking in some current from Vcc through the upper resistance, that will distort the voltage. The instructions for the a/d input recommend an input impedance in the ballpark of 10 kohms I believe, not megaohms.
One way to circumvent this problem, is to take a reading, and ignore it, and then take another reading. The rationale for this, is that when you take the second reading, the capacitor in the a/d converter still has most of the current that it sucked in the first time, so it doesn't need to suck in so much current the second time, so the second reading will result in less distortion of the actual voltage divider voltage that you are try to measure. I have followed this suggestion before and it seems to work.