Had this problem with a bad N adapter, got it exchanged and all was good, I know you had the TiVo exchanged but sometimes two problems happen at the same time, you can test out the N adapter on a laptop computer if you shut off the laptop wireless adapter and check the Internet speed using just the N adapter connected to your RJ54 jack, you can also make sure that the N adapter is connected to your router correctly.I have 2 Premiere XLs and the Tivo wireless N adapter connected to one and the second connected to my Verizon AcionTec wireless g router. Multiroom streaming worked well with my original units, even HD programs transferred in just a few minutes and played through successfully.
However, Tivo swapped out one unit for a refurb due to an esata problem. The new unit sees my other unit's program list, but takes about 4 days to transfer 15 minutes of a 30-minute HD program and the rest is unwatchable.
Customer service said it may have been too soon for this feature to be usable and suggested unplugging both units and forcing a connection to the Tivo service. This did not help and it has now been over a week and the problem continues.