It seems that AT&T wants to charge twice for the same traffic... once from their customers, and once more from Google or any other high traffic site they think they can intimidate.
The fix for this problem is very simple. Google should just redirect queries from AT&T customer IP blocks to a special page explaining what is happening, and how they are being threatened. They would, of course still allow the search.
If people smell greedy bastards threatening their Google, they'll react rather quickly and with overwhelming force.
This would be a rather simple, and VERY direct power play. Google, of course, would win. It would do good things for their image as well.