I was having the same issue, even with my wife's 3GS sitting right next to me working perfectly.
One thing I noticed was that it only occured when my iPhone 4 was showing full signal. I'm no stranger to RF, radio, antenna and electronics design, and have run into situations where I've needed attenuators inline to reduce the incoming signal and avoid overdriving a receiver.
At first I thought that might be the culprit, with the new antenna system providing better signal, because honeslty for me the 3G issues had only come up at full signal.
As it happens I wound up calling AT&T about the issue while thinking about this and they wanted to try re-provision my SIM before escalating my call.
Short version: A short wait and a reboot later I've had no issues with 3G since, at full signal or at one bar. I am seeing 1.3-2.0Mbs/down with about 1Mbs/upstream.
This was an issue from the 2nd day I had the iPhone 4 (didn't get to use it on 3G on the first), until I made the call. And it's been fine for a couple of days now (I've been fairly OCD about testing it).
Hope this is useful ... it worked for me.