From my experiences, Vonage and TiVo don't mix well at all. I had both parties on the phone at one point and no one knew how to make it work. I eventually broke down and located a WiFi dongle on eBay and that was that. Now that TiVo wifi's are in every store, you don't need to go on the wild goose chase I did, comparing printouts from tivo.com to the box I had in my hand in Best Buy.
Even if you don't have wifi, a cheap $30 linksys router would still make sense than spending countless hours trying to make Vonage work. I do know though that TiVo on the VoIP I have (and work for) does work but we don't service Virginia.