Streaming video between 2 Replay 45XX series over LAN help

How is your network connected..wired or wireless? If wireless that may be your problem. Some wireless is not fast enough.
Apparently streaming video takes a good bit of bandwidth. I had similar problems to what you describe, although not quite as bad. I solved my problem by setting up my network a little differently.
I have a two story house sitting on a basement. I had one Replay on the 2nd floor, one on the 1st floor and a DVArchive computer in the basement. My router was on the 1st floor. There was a switch (needed because I had more connections than the router would support) in the basement where most of the computers and all of the Replay and DVarchive were connected. Although I was able to stream, I had lots of issues such as the ones you describe. Even when I could get the show to stream, it would stop and give me a "video unavailable" error every few seconds.
I corrected my problem by moving my router down into the basement and hooking the Replays and DVarchive directly to the router. It all works great now. Apparently either the longer cable runs to the switch and back, or just the switch itself was creating enough of a delay to give the Replays problems.
I might have been able to correct the problem just by using a different (possibly better switch), but my solution cost nothing and works for me.

The memory issue is a known issue on the 5xxx's. I'm assuming you're getting some problems with your 4xxx's. Maybe trying sorting your shows into categories to make the list a little smaller/easier to load into memory.

Having too much in the guide is a big problem on the 5xxx series. One solution is to run a couple of instances of DVarchive and download all of the shows to the dvarchives to split the load. If you have lots of 30 minute shows at low quality, archive them to DVD. (12 of those should fit on 1 DVD) Having the other replay off seems to help as well.

my suggestion would be to try connecting the replays to the router and then trying to stream some shows and compare. then connect one replay to your switch leaving the 2nd to the router and try streaming again. I am curious if the problem is the switch itself.

The gigabit switch won't make any difference because the network cards in the replays are 10 or 10/100. I upgraded my system to complete gigabit speed and I saw no difference. I still get drop outs. I have a feeling that the buffer in the network card is not uniquely set up for the speed of the hardware buffer.

I had the same problem for a while here with my 4500s - able to see show listing, but unable to stream either way.

One day when I opened my DVArchive, I noticed that one 4500 had a "Timestamp" off by 2 minutes. No matter how many times I connected, it refused to update the time to the correct time. I switched the DNS server to the same as the one which had the correct time, and it was able to "Set clock" to the right time.

Problem solved! I'm now able to stream. No more "Unable to contact remote unit" error messages. Try to confirm that your Replay clocks are syncronized and let us know if it works. Good luck.