Sorry for bringing this up again, i know it's been a while.
I was testing myself a DHT11, and i found that it's very sensitive to supply voltage.
I found that it's working at 3.3V as well so i powered it from the 3.3V pin from Arduino.
I used a relay too and i found out that the relay was taken a little more current than what i expected, but enough to tamper the sensor readings. I had that bounce between the 3 degrees as well.
But changing the relay power source was a great idea, and now the DHT11 is stable.