This used to happen to me all the time when I had a linksys router and was using the linksys adapter on the tivo.
It has something to do with the tivo software caching the wireless key and network name.
Log into the router, change the wireless network name
Go through the network setup on the tivo again, making sure to choose the new network name.
This has worked for me consistenly every time. Then again, I now have a netgear router, which hasn't caused me any issues in over 2 years with my tivos.