I had this issue with two replacement batteries, tried the SMC reset, PRAM reset, etc. One of the two responded for a little bit (24-48 hrs), but then would fall back into the "replace now" status and the laptop would not stayed on under battery power. The other battery never responded and immediately said "replace now".
Working with support, I received a cross ship of a third battery and it has worked flawlessly - no SMC reset, no PRAM reset, just replaced and powered up and works great.
So, my suggestion is report the issue back to support and get a second (third, fourth...?) sent out to you. Can't say why, but seems there is some percentage of bad apples in the mix.
Note that I used coconutBattery to document the battery situation with replacement #1 & #2 for support. Gives a series of good data points that demonstrates the status with notation of the battery production dates and cycles. When you think you have a good battery, though, make sure you use it for longer than a couple of days before you call it a victory.