If you haven't, I'd try rebooting your router and TiVo's. Turn off everything. If you have a DSL or cable modem power that up first and let it come fully up. Then the router if the modem and router are combined, then this step is uncessary but otherwise then the router. Finally the TiVo's.
You might also go into the TiVo networking setting and let the machines re-discover your network.