So I just spent an hour trying to properly configure TiVo so that it would connect to my secure wireless network, and here are the details for the next guy searching on Google for this…
Wireless Router: Linksys WRT54G
USB Wireless Adapter: Netgear WG111
Secure Wireless Settings: WEP 128 bits
The problem was that my router was setting the WEP key to the third key choice (I get 4 different keys for each passphrase), and TiVo only works with the first one. The router was also set to ‘Auto’ on Authentication Type on the “Advanced Wireless Settings” screen, and I had to change it to ‘Shared’.
After changing the two things above, my TiVo started working right away and it is now downloading updates.