Make sure you do a restore through itunes and see the message that you unlocked the phone.
I got the unlock for both my iphone 4's. They say to do the restore through Itunes approximately 24hours after you get the final confirmation email. I did it right at the 24 hour mark and assumed it worked.
Without having another sim to test, I just did another restore (right after backup when changing over to iphone5) just in case and Itunes then gave me a message congratulating me on unlocking my phone.
I assume I just didn't wait long enough the first time around and it hadnt worked.