Was the spare charger an Apple original charger or an inexpensive "dollar store" charger? I ask because cheap chargers can damage the charge circuit inside the iPhone.
Now when a phone has charging issues, normally the first thing to try is a new battery, as that is the weakest link. It is possible that the replacement battery is dead. If you can install a known good battery and it does the same thing, then your problem would be logic board related, which would require a micro-soldering repair.
In your situation, I would return to the shop that replaced your battery and have them test it or try another one to help isolate the problem.