Ubuntu Networking :: Wireless DNS Resolution Fails?

When connecting to any wireless network, DNS lookups completely fail to work. Over a wired connection, there's no trouble.

I can ping machines by IP address, and I can dig and nslookup domain names using the DNS servers assigned by Network Manager or by myself. When I try to ping by domain name, however, nothing happens. Similarly, I cannot ssh into machines by domain name or browse the web.

My wireless card (Intel 4965AGN) is managed by Network Manager. The issue is seen regardless of whether DNS servers are obtained automatically by DHCP or assigned by me through Network Manager. This started about a month or two ago while I was using Maverick and presents again with Natty. I dual-boot Natty and Windows 7, and everything works fine in Windows.

Somehow, this seems to be linked to Nautiluswhile connected to a wireless network, Nautilus won't open, my desktop icons won't show, all that jazz. If I'm connected to a wired connection at login time, Nautilus works fine.

I've managed to workaround the browsing issue by setting up an ssh tunnel through a machine at school and forwarding Firefox's DNS resolution through that tunnel. But I'm at a loss as to how to resolve the core problem.

Here's some diagnostic info. I've modified my IP and hardware addresses below.

Code:
$ ifconfig wlan0
wlan0 Link encap:Ethernet HWaddr 00:1f:3b:27:be:35
inet addr:xxx.xxx.38.96 Bcast:xxx.xxx.39.255 Mask:255.255.254.0
inet6 addr: fe80::21f:3bff:fe27:be35/64 Scope:Link

[Code]....

I've tried all the basic steps killing and restarting Network Manager, renewing my DHCP lease using dhclient, restarting /etc/init.d/networking. I'm at the end of my rope, though, and ready to reinstall. I'd be much obliged if anyone can think of a less "Microsoft" solution.