i had the same issue with AT&T and the iphone 3GS in manhattan. They replaced it for me b.c my att Blackberry didn't have any issues but the iphone did. I showed them calls that i never got but had a voicemail for. Also i told them how i was dropping calls all the times and even worse i wasn't even getting some calls.
They replaced it for me on the spot without a genius bar appointment, took them maybe 15 minutes at the 5th ave. NYC flagship store. Ive had every iOS device they make, and i get at least a new computer every year, and i have a substantial business acct with them. So idk if that affects their decision but they have never done me wrong and it's mainly why i stay with them.