TMP36 x Voltage input in arduino
You can neither correct it in software, nor use a diode or resistor to drop the voltage if you don't know the cause, or the error function. You get 44° instead of 22°. What would you do to solve this? Divide by 2? Would a reading running on USB of 15° also result in 30° when running on the batteries? A diode would be a bad solution in any case.  

My first reaction was that the batteries would give a too high voltage. The first line of the datasheet says 2.7V to 5.5V operation. Now if those were Alkaline batteries you would have 6V, that's outside specifications, and then anything can happen. Always make sure you're within specs before you start looking at other things.
But you say they're rechargeable, that's probably NiMH, at 1.2V per cell that would give you 4.8V, almost the same as the USB's 5V. That can't explain it.  

I realize it will be a simple schematic, but still: post it here. We'll need to have a look at every possibility. In the mean time, measure the batteries' voltage and report back.