Here is a generic procedure which fixes a couple of known bugs in nameserver information handling.
Is resolvconf installed? If so then do the following.
sudo dpkg-reconfigure resolvconf
If it is not installed then do the following.
sudo apt-get install resolvconf
Now that resolvconf is installed correctly, reboot so that resolvconf will be provided with nameserver information.
If name service is still broken and you are using NetworkManager to manage networking then open /etc/NetworkManager/NetworkManager.conf in an editor and comment out the line "dns=dnsmasq". To comment it out, put a '#' character at the beginning of the line.
gksudo gedit /etc/NetworkManager/NetworkManager.conf
Next go into the connection editor and make sure that the connection you are using is properly configured. E.g., most often "network indicator | Edit Connections... | Wired | Wired connection 1 | Edit... | IPv4 Settings | Method" is set to "Automatic (DHCP)" and no "Additional DNS server" addresses are set.
Then restart network-manager.
sudo restart network-manager
Now confirm that the expected nameserver address(es) appear in /etc/resolv.conf.
If you aren't using NetworkManager to configure interfaces and you are using
ifup then edit
/etc/network/interfaces and include
dns-search lines in the appropriate
iface stanza as needed. Make sure that /etc/resolvconf/resolv.conf.d/head only contains comment lines and that /etc/resolvconf/resolv.conf.d/base and /etc/resolvconf/resolv.conf.d/tail are absent or empty. Then
ifup the interface. Confirm that the nameserver address(es) that you added to /etc/network/interfaces now appear in /etc/resolv.conf.
If name service still does not work then there's most likely a local problem: a misconfigured DHCP server, for example. Another known cause of problems is third-party VPN clients which trash the symbolic link /etc/resolv.conf. If your LAN seems OK and you aren't using third-party networking software then file a bug report against NetworkManager or resolvconf, whichever you think is more likely the culprit.