Symptoms included pings that would fail, I couldn't point my browser at web sites hosted on local servers, NFS mounts failing, and other general mayhem. Interestingly, while the MacBook was experiencing the problem, I'd run nslookup or dig on the DNS entry in question at a Terminal prompt, and it would return the correct information.
My network has a Fedora 11 box acting as a server with BIND DNS and DHCP running on it. Originally, I'd been publishing both my BIND and internet router as primary and secondary DNS servers respectively via DHCP. After removing the internet router as a secondary DNS, leaving only the BIND DNS, my MacBook magically began to work again.
I don't know the actual root cause and your milage may vary depending on your network setup.

