Seconded on it likely being a DNS issue. Ever since all current OSes rolled out the security patches to implement DNS source port randomization
, I've been experiencing symptoms similar to those described in the OP for any systems that run through my Netgear WGR614v5 router. I strongly suspect (but haven't proven conclusively) that the Netgear's NAT routing is getting confused by the port randomization, and dropping a lot of DNS responses on the floor. Unfortunately, Netgear appears to have abandoned this router; they haven't issued a firmware update for it in nearly 5 years.
I suggest you check whether there are any firmware upgrades available for your router, and see if that helps.
In my case, I've mitigated the issue by setting up a local DNS proxy... but the real solution is to ditch this POS router. I'm actually planning to do some tests tonight using one of my Linux boxes as my Internet firewall/router instead of the Netgear.