Same problem here:
I have Win 7 Pro 64-bit. I've had this problem intermittently during cold boot for the last few months, since about mid October 2010, and I KNOW it is related to a Windows update that occurred about that time, because back when the problem first began, I tried a system restore, and my internet connections on restart then always succeeded, and I had no other installs of any kind since the problem began. But, I want my Windows updates. So I currently have all Windows updates, and of course, the intermittent connection issues too.
To get around the problem, I have been doing a restart(soft boot), and 95% of the time, the restart works. The other 5%, I have to restart a second time. I also have Windows 7 Pro 32 bit on another pc on my home network, and that has never had internet connection problems.
fyi, coming out of full sleep mode (did I mention I **LOVE** Windows 7's improved sleep?), I never have issues - at least not so far.
I'm going to try the suggestions here, and report back with results when I have time.