Did you have it replaced at an Apple Store or by a third party? I'm deciding between the two – my gut is to go with the Apple Store, but the apple website makes it sound like it could take up to 5 days, which is too long.
However I've had batteries replaced (different phones) at the Apple Store before and it took about an hour.