This may be related. I could not see my Mac from the TiVo and I changed the Mac name in TiVo Desktop system preference. The Mac then showed up on the TiVos. I agree, this should just work, sometimes a reboot of computer, sometimes a router reboot.
Toshiba SD-H400, Tivo Series 2, Tivo HD, TiVo Series 3 THX, TiVo Premiere (All upgraded with extra HD goodness) and an XL4.