That is something I've seen, albeit rarely, with every phone I've owned. I get excellent HSDPA signal at my house, but there must be some interference from something, because, maybe once a week, my phone will think it is connected (3 or 4 bars of "H"), but any attempt to initiate a data connection fails. You can see the outbound arrow light up, but nothing comes inbound.
I find that the easiest way to correct is to put the phone in airplane mode, then immediately turn airplane mode off. For me, this works 100% of the time.
I had exactly this same problem with my BlackBerry Bold and my iPhone 3G before that. I'm on Orange in France, and live in Paris. The version of the software does seem to make a big difference. With the Bold, I ran 4 different versions (three 4.6 and a leaked beta 5 version), and even though I saw the condition with all of them, I saw it only once or twice on 4.6.167, and only once or twice on 5.0.230. On the iPhone 3G, I saw the problem only rarely. With the Milestone, I've seen it perhaps 4 times in 3 weeks, though to be fair, it happened 3 times in the first 5 days, and only 1 time since.
Good luck - I'm hoping that the imminent update helps!