You may also want to try cycling power on your modem, router, and Tivo. Unplug all three, then plug in the modem and let it power and connect on fully; then plug in the router and let it power on and connect fully; then plug in your Tivo.
*But* you say *It cannot be the modem or router; all my other devices are working fine!*
Yes, but sometimes weird network stuff happens, especially after a power outage when things come on all at once. Restarting all three may clear up whatever the nagging issue is with the Tivo. Worst case scenario is that you waste 15 minutes and you're right back where you started.