HT5014: iPhone: About unlockingLearn about iPhone: About unlocking
Did AT&T notify you that your unlock was approved?
If yes, when you Restored it in iTunes did you get the message, "Congratulations, your iPhone is now unlocked"?
And if yes to that, was your iPhone previously hacked/jailbroken in order to unlock it?
If it was jailbroken or hacked to unlock it prior to obtaining a legitimate unlock, it may not be able to process the unlock/restore properly and it may not be able to activate at all, even with an AT&T SIM. If that's the case, you're on your own.