Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
I think it might be a band issue. Verizon iPhone 5 has bands that support Verizon but the gsm bands it uses might be different from what at&t uses in your area. Btw, at&t has grandfathered its 2G service last year.
 
With AT&T, you have to call and update the IMEI so that you will get LTE. This can also result in the phone showing no service. Try calling cust service and having them update the imei on your account to the 5s's.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.