Constantin:
If the issue turns out to be heat-related, I see two approaches.One, measure on-board temperature with a LM35, TMP36 or similar analog temperature sensor. Alternatively, a DS1B20 might work great too. If the influence is somewhat linear, you could use the temperature sensing to correct your readings.
My preferred choice would be to read a series of reference resistors. Use their output via a least squares approach to correct your offset and gain on the ADC and you can continuously fix the problem.
I do have an on-board temperature sensor - DS1631, it resides on the Shield. Forgot to mention that the resistors are also on the shield (SparkFun Proto Screw Shield). The DS1631 readings are 100% reliable so far.
Also have another temperature sensor (DS18B20/OneWire) in the front of the bike. Arduino is under the bike seat. The readings between them are not that different - about 5F at most (which makes sense, given their locations).
I have found a workaround to the problem - I do recognize the 1st gear consistently (because it always has voltage < 1.5V), so I know 1st Gear should be 1.33V (normally) and I use a compensation of the difference. e.g. If the 1st voltage gear reads 1.00V by Arduino, I know that it should be actually 1.33V and therefore add 0.33V to all other gear readings. It works, but I would like to understand why this happens.
As for the other option, thanks but I ran out of Analog ports space..they are all used..