I'm not able to replicate the issue on my iphone 4. I've attempted at home and at work, in which I drive 30 minutes away. I would even say it is somewhat rural where I work and the reception isn't always the greatest, but have had no problems.
Has anyone tried to reinstall iOS4 to see if the problem continues?