They've been having a hard time since the late 1990's when they introduced the "one rate" plans and basically oversold their coverage area in NYC.
I distinctly remembering long articles talking about how the networks were so saturated, dealers were still activating phones on their network knowing the customers wouldn't get a signal and would have zero reception in NYC, even after being told by several courts to stop signing up customers.
Here is the text of the class action lawsuit that made it all the way the NYC Supreme Court: http://www.whafh.com/modules/case/docs/2556_cid_3_AT&T%20Cel...
EDIT: some of the articles I alluded to are listed in the class action starting on page 9.