Reset the network settings- reboot the phone and see if that helps. I was in NYC in the spring and had really good coverage even in the middle of Central Park.
NYC's 3G map shows full coverage, but it doesn't take into account connection density. Their towers are saturated. Fortunately, they claimed relief was coming to major metro areas like NY and SanFran by the end of the year in the form of newer, more capable towers. Hang in there.
in congested areas such as nyc im not surprised. there are SO many people feeding off those towers that they probably just simply cant handle it. i really only saw issues with my service when i was in concert venues. nokia theater was pretty spotty from what i remember and thats in the heart of times square and is underneath the mtv studios. im sure itll improve over time