Just to make sure it is DNS and not some unrelated fluke, have you tried putting the default settings back on one of the PCs?
If it was the DNS fix for sure, you had better tell your ISP that either their DNS servers are FUBAR or the first hop DNS settings on your router are incorrect and need changing as you can surf the net just fine by going directly to Google's DNS servers.