It's max is/was 144kbps. I never got over 100kbps with Edge a few years back. I'm sure Edge has evolved a bit since the last time I was using it.
I think that Verizon does include 1xRTT when creating their coverage maps, and if they are not including AT&T's Edge service, which is theoretically faster, than I can see the problem that AT&T has with these advertisements.
Edit: I certainly don't miss those days. If I had to go back, I think I would miss losing high quality streaming Pandora more than anything else.
3G Speed Test