"Temperature" screen even when the phone isn't hot?

After changing my battery, the battery works fine again, but a few days after I changed it, I started having "overheating" problems. These are not actual overheating problems, because the phone isn't hot, but it keeps showing me the "Temperature" warning and telling me I can't use the phone until it cools down.

This has happened fairly constantly at seemingly random times, and thus far, the phone has never been hot to the touch. It even happens while the phone is physically cold to the touch (outside in 20 degree F weather, for example).

Today I can barely use the phone, it just says "Temperature" pretty much all the time. For a few seconds, sometimes it goes back to the normal swipe-to-enter screen, but it goes right back to the Temperature warning screen after that.

Everything else on the phone works, so I'm sure the repair went smoothly otherwise. Again, this took a few days to start showing up.

Here are the relevant facts, along with some things I've tried to troubleshoot and such:

• I installed a CPU monitor but nothing seems to be taking up the CPU or anything like that.
• I've killed all the background apps and it still happens. I've also left it on airplane mode for hours and it still happens.
• I've tried a full reboot, as well as a restore from backup.
• The battery is not draining faster than normal or anything like that.
• This phone has no history of water damage and i don't sweat a lot or anything like that (nor do I keep it in my pocket).
• I've never seen this temperature warning before swapping the battery.
• I don't use a protective rubber case or anything like that, the phone is just sitting on my desk.
• Charging the battery no longer works because it doesn't seem to charge while it's on the "Temperature" screen.
• I saw no corrosion inside the iPhone at all when replacing the battery.

I'm running the latest firmware (6.0.1) and it's not jailbroken.

Thanks for your help!