Been having the same problems in Chicago. Downtown, Wicker Park, etc. Go from full 3G to E to No Service and all back around, from 1 bar to 5. It doesn't jump around this much in smalltown Louisiana.
Tonight, a group of us sat at a restaurant table on a main Chicago street. Five of us had iPhones, and we had to play the "stand by the glass door" game to get reception. Otherwise, our phones displayed a consisted No Service all the way around.
Meanwhile, the guy with the Verizon phone kept a full 3G signal the entire time. Someone remind me when the AT&T exclusivity ends?