It sounds to me that you’ve got either a network or DSL modem problem. On the Tivo support forums they describe the problem a bit better:
N07: Gateway not found
The gateway (router) could not be located. (N07)
1. Please make sure your network is operational and correctly configured.
2. If you are using an encrypted wireless network, check that your network password is correct.
3. Try rebooting the gateway (router).
4. If using a TiVo Wireless N adapter for the first time, it may not be set up properly. Please see TiVo Wireless N Adapter Setup for instructions.
Further searching provided:
Failed while negotiating can be caused by several things.
One possibility is the existence of a proxy server or parental controls device between the TiVo and the TiVo Service. This could be in your router, the broadband modem, or your ISP's infrastructure. The fix is to add exceptions to the proxy server or parental controls to make sure it does not block or cache any transactions with the TiVo Service. For your router, you will have to do this yourself. For your modem or ISP, a call to your ISP is in order to see if they have such equipment or capabilities and to see if it is properly configure to not interfere with your TiVo.
Another possibility is packet fragmentation problems between your TiVo and the TiVo service. This can be caused by mis-configured our malfunctioning hardware in the data path. Again, it could be in your wireless router, the modem or your ISP's equipment. One thing you can try for this is to set a lower value for MTU setting in your router, if it has one.
Finally, it could be a firewall in that same path, with all the same actors. If there is a firewall that blocks outbound ports, then it must be configured to not do that, or to except your TiVos, or your entire home network. Again, if it is your router, you will need to do it, otherwise you will need to contact your ISP.
In a perfect world, Tivo tech support should have mentioned this to you. The truth of the matter is that almost all tech support has gone to the dogs. They put the burden on their clients to use google to find solutions. In the past month I’ve had to do this for World of Warcraft, Norton’s Internet Security, Microsoft Visual Studio 2010, and a number of other lesser-known programs. It is a sad comment on current support for paying clients, but it is becoming increasingly common.Edit: It sounds like I'm apologizing for Tivo's tech support. Far from it. I'm just lamenting the state of the world, and recognizing that Tivo isn't the only outfit who's support has slipped badly. It really pisses me off that we're at this point and it is only getting worse.