If you just run the numbers a 31" tire with a 1:1 transmission output gives you 2674 rpm at 60 mph. Assuming a 1.1OD ratio that would drop to 2430 rpm. Your stated rpms are way off, and you should have lots better power on the hills. One question - Did you correct your speedometer gear when you went to 31's? Can you check your speed with a GPS to confirm actual speed?

Backing off to 29" tires is the wrong thing to do, for looks and off-road performance if nothing else, but it will also kick your rpm higher. I'm running 33's on my TJ with 3.73:1 gears, manual tranny.