василий иваныч, и другой у которой 5-ка оказалась залоченной. А вы после того как симку вставили, восстанавливали ли телефон на заводские настройки? Если нет, попробуйте, в худшем случае, ничем не рискуете (Settings -> General -> Erase all content and settings). Симку русскую держите внутри при этом. Делайте это где есть вай-фай, если симку так и не увидит... Иначе, если такое пробовали, и если исключить явный брак в случае с 4S (маловероятно), то у вас 2 варианта.
1. Посложнее - позвонить в at&t, назвать IMEI, они проверят что тел. куплены без контракта и должны быть разлоченными (как 4S так и 5), создадут case #, дадут номер факса, на который вам надо послать чек (где видно что тел. куплены без контракта). В течение недели должно придти письмо, после чего восстанавливаете тел к заводским настройкам с российской симкой, и он разблокировывается. В Apple не звоните, смысла нет.
2. Полегче, стоимостью $15 - 20 -- на ebay есть несколько зарекомендовавших себя продавцов (псевдо)официальных анлоков. Ваш IMEI просто добавляется к списку "хороших" телефонов, и получается kinda factory unlocked. Disclaimer -- этот метод работает, подтверждено авторитетными, знающими людьми. Рекомендовать или поискать конкретного продавца не могу, лично не пользовался. Можно найти упоминания таковых на форумах типа macrumors..
... И в конце-концов - вы проверяли IMEI на предмет залоченности на многочисленных сайтах? Вряд ли могу давать ссылки, но поищите по ключевым словам iphone imei lock status check.. Если покажет unlocked, значит либо делаете что-то не то, либо телефон каким-то образом не отображается в базе данных сим-фри телефонов.