I can tell you that it may well be the router. If you test everything out, you will find that you can make the connection with out the router just fine, and with the router with issues.
The same problem happened to me, I tried everything, from a new Linksys (I claimed it was defective) to a different ISP. I even moved in the mean time and that did not clear things up. Then just as magically as it appeared it went away. Now I am running with the linksys befsp41 and with a befvp41 just fine. The latest firmware of course, which may or may not have been both the culprit and the solution.
I do belive that this problem can have many sources, so I do not put full blame on Linksys, I still use them even, but I do think that it can in fact be the little gateways that are the issue. I used to have to reset my gateway every 5-10 minutes while playing online games. Now I run VPNs from both a client through th egateways and from the vp41 itself and never have a problem with them. I have used Charter cable in WI, Time Warner in WI, TDS in WI and Sprint Broadband in CO. I have experienced this issue with all of them, in 4 differnet locations in 2 states, with 2 routers (1 model then BEFSP41). The VP41 has yet to give me issues, but the SP41 has been good for nearly 5 months now too.
I know that the routers themselvs stopped responding since I have a workshop full of machines, from 2-10 at any one time, plus 4 of my own, and they would all lose connectivity when I would play online. I thought that there was too much traffic for the tiny little processors that they must have, but I see no reason that it would happen durring games and not durring file sharring apps which use up my full bandwidth almost the entire time they are running, or why not durring concurrent web traffic from multiple machines at once while uploading and downloading files. But that was the nature of the beast.
If anyone has a good idea why other linksys equipt tunnels happen to fail, let me know. It is strange though that everyone seemed to have the linksys here, except maybe phoneguru.
Eddie Venus