We are seeing I think something simular,people booting up and not resolving names until we do an IPCONFIG release then a renew. Looking at it this morning, we believe it is on Windows 2000 clients only, and are testing a couple things especially with the DNS client that you can run on a 2000 client. They are getting an IP address, the last one they had from the DHCP server but no name resolution, we believe the card isn't coming, because of some suspicious events in event log are saying this, so it try's to use it's client DNS, the card comes up uses it's last good address, but doesn't try using the DNS server because it thinks it will use the client DNS. Once we release/renew it sees the DNS server and works fine.
Sounds a little related to yours, I wanted to throw this out to see if you are finding the same thing, and to make sure you haven't found anything with the 4000's which we also over Labor Day installed.
I will look for any new developments from you.