I got a variety of different problems after replacing my 3GS battery (iPhone 3GS, iOS 6.0.1). I was pretty close to trash it. But I found a way to get back to life and want to share the story. My conclusion is that is seems that the software (apps & iOS) is dependent on correct power management. With a battery replacement is that radically changed. First of all get a good replacement battery, no fake ones. You get what you pay.
After replacing the battery the indicator wasn’t correct but I could live with that. Resets (home button + sleep/off button for 10 sec) and restores via iTunes didn’t help. Then started the problems. After 2 days the phone began to shutdown using the camera/GPS or simply getting a call. Annoying, especially with a new battery.
I tried everything you can read on the net. Nothing worked, it just got worse. Cleaned every connector. Put the old battery back, didn’t work either. It was dead.
My final call was this: put in the new replacement battery and tighten all screws properly. Restore the phone from iTunes, but DO NOT, I repeat do not, restore the data from the backup from iTunes. Restore the iOS but when the iPhone reboots and iTunes will continue with coping of data (apps, calendars, music etc) ABORT that process. The data from your backup will corrupt your iPhone. Abort the process, unplug your phone and let it start up alone like a new phone. You need a clean start with a new battery.
This means that you need to download your apps again. I did that very carefully (perhaps too carefully, but I did want to know if any app corrupted my phone). I have now synchronized my calendar and contacts via iTunes but I have not restored any apps. It works flawlessly. The battery indicator is even back and correct!
I’ve got it all back: a working iPhone w/o shutdowns, a battery indicator and a new, fresh battery.
Good luck with your battery replacement. ;-)