I had an unlocked iPhone 4S (which was unlocked through an ebay seller this past weekend) that was replaced on Monday. The genius or whatever you want to call her, basically told me to wait 10-15min before turning it on so the system can have time to unlock my phone. Well 15min later I turn it on and it wouldn't activate. It was asking me for a valid sim card (I did have my T-Mobile sim in there, which was working just fine with the phone that was replaced).
Once I got home I plugged in the iPhone to my laptop and restored from backup, didn't get the congratulations message this time around but it was still unlocked.