Some Just Won't Work
It's just a fact that some network devices simply aren't compatible with a particular ISP's network. Although 90 percent of the products you might run across will be compatible, it's up to you to determine which ones won't work. That means contacting the ISP or visiting their website for a list of compatible equipment. In your case, AT&T told you the Airport wasn't compatible, so trust them on this on ask for a list of compatible routers. I'm not sure how AT&T works, but hopefully they aren't only providing you a list of their own supplied equipment.