iPhone 4S shutting down 20-30 % - battery already replaced
Few ideas:


Have you tried a full blown factory restore? 
Are you SURE everything internally on your phone is secured and exactly as it was when you first opened it? Might be worth it to open it up again and double check.
Have you contacted the battery seller? I've personally never heard of 'em, but then again I've never been in the market for a new iPhone battery. I would contact them and let them know about the issue. It very well could be that you were sent a dud. 
Last resort: Get it replaced. Not sure what would've gone wrong with the battery replacement, but there ya go. Contact your cell phone service provider or an Apple Store and see if you can either get it fixed by them or get a replacement.