Bad batteries can and do happen. While there may be a rogue app that is gobbling up your battery, it's really unlikely that software could cause your phone to shut down at an indicated 20% charge - that's almost always a sign of a failing battery, or something wrong with phone hardware. My first guess would be that your replacement battery is failing. If it's from a reputable dealer you should be able to do a warranty exchange of the new battery if it died after a month.
While anything is possible, I very much doubt a factory reset is going to do a lot of good. You could try clearing the system cache (power down, POWER-HOME-VolumeUP to start, a menu eventually will come up, choose the clear cache option). That's harmless and easy to do - though I kinda doubt that will help either.
I'd start with trying another battery, especially if you got the one you have now very inexpensively off eBay or something. Most of the cheaper batteries from eBay are perfectly good, many are actual OEM, but there are lots of copycats out there, too. Caveat emptor.