I know this sounds silly, but it sounds like it could be a network problem.
I would check with Warren over on the mailing lists to see if your TiVo is actually calling home, and if so, then start travelling down the line and see where else the problem could lie.
One step at a time
Cheers
Bookmarks