I think this is a problem with name-server configuration.
Your name-servers should be configured automatically.
try:
$nslookup
www.google.com
see if any name-servers pop up.
If not contact your provider for name-server ips, so that you can configure them manually.
Or make sure that you have selected automatic configuration of name servers.
I have not used Ubuntu, so I am not sure of network configuration utility available to you.