I attempted a battery replacement on my daughter's iPhone 4. After a bettery remove and replace (not the R&R we all hope for!) her phone did similar things as yours.
Check the connector on the main board your battery plugs into. Be really careful when you do this and don't remove the battery again if you don't need to. During the R&R, I managed to break the surface-mount solder joints and remove the main board side of the connector with the battery lead. I don't know if the connection was a pre-existing condition, or if my removal technique was sloppy or overly forceful.
I rectified the condition by upgrading my 4s to a 5 and giving her my "old" phone. If you're eligable, now might be a good time to consider a carrier-subsidized upgrade. If you're not, look for a friend with a 4s who is eligible for an upgrade but hasn't exercised it yet. See if you can pay for their upgrade fee, getting them a new phone and you a $200 replacement.
Good luck!