Has your ISP or router changed? It seems similar to a problem some have with IPv6.http://ubuntuforums.org/showpost.php?p=478267&postcount=8
(and the rest of the thread.)
See if the command (run it terminal without quotes) "host www.google.com" succeeds quickly. If it does, then it is a browser problem, most likely.