This sounds like a DNS problem.
The file /etc/resolv.conf should have the nameservers IP addresses in it. Nameservers IP's can be supplied by your ISP or you can use public free ones.
You did not say how you have your network set up. Some routers, will pass to the host systems DNS IP's and the linux systems will store it in /etc/resolv.conf. This happens when you do a DHCP request.
You can try a manual update of /etc/resolv.conf. Enter these addresses into resolv.conf ( you have to be root ) and save the file, and try your network connection again.
These are all public nameservers. You can use your ISP's in there place. You can test it with a browser, or try a ping to something like yahoo; 'ping www.yahoo.com
' . If the ping works, the name service resolved the name to an IP.
Resolve.conf gets overwritten when your system gets an IP in most cases. So it may be the your router is not set up correctly.
Hope this helps.