A lightbulb just went off in my head...
I have been following the thread (intermittently, like the problem) but the last post about the router got me thinking about a somewhat similar issue I had at home when my daughter got a new laptop. It may not be related at all, but it's a nice thing to know, so I will share.
I had been running for several years without problems. A couple of WinXP PCs hardwired through a switch or two, a couple of XP laptops, some Linux Tivos and my wife's Win7 laptop. About the time my daughter got her Win7 laptop, both she and my wife started having connectivity issues. Win7 would suddenly say that my router was an "unknown network" and disallow internet access. Sometimes it would be my daughter's, sometimes my wife's, sometimes both. Doing a "repair" would sometimes fix it. I finally discovered that the problem would occur only when both of them had their laptops ON at the same time (for a time) and then one of them turned theirs off. Then the other one would stop connecting to the internet. "Repair" would only then work if the other laptop was still OFF.
After beating my head against it for days, I figured it out... When ONE Win7 computer ONLY was connected to the router (wirelessly) it would setup an IPv4 connection and work fine. If that laptop was still powered on and the OTHER Win7 laptop was powered ON, it would first look for an IPv6 (start with the newest tech, right?) which it would find peer-to-peer with the other Win7 laptop, then share it's IPv4 connection to the router and ergo the internet. When the FIRST (connected) Win7 laptop was powered off, the SECOND one wouldn’t release the IPv6 association with the router via an internal IP, but was still connected to the router’s SSID, but reported it as "unidentified network" and blocked internet access. Doing a “repair” (only with the other laptop OFF) would fix it, until the other computer connected to THIS laptop (IPv6) and THIS first laptop then got shut down. Then the problem just moved to THAT laptop.
I was blaming Win7 and started rolling back updates, which didn’t help. It finally dawned on me that my cheapie Airlink101 router was quite old and may not support IPv6. I checked, and it didn’t. No updates available either. A quick trip to Fry’s for a new BelkinN+, and no problems at all with connectivity since.
Bringing the light-bulb moment back around, have there been any other hardware changes to your network? I think you tried another router, but what about connected devices? Disable those for testing?