I reckon you should try a T-Mobile SIM card in it. This would prove that it is definitely unlocked. Have you tried another AT&T SIM or any other for that matter. If it rejects another SIM, iPhone may be faulty.
Therefore virginize iPhone and return him back to the shop where you bought him from and get a replacement.