Firstly, is there a good reason to use rsh instead of ssh? I've seen plenty of posts burning the OP for not using ssh based tools, so I won't do the same here, but I would be interested to know why you want to use rsh instead of ssh.
Next, it sounds like a firewall issue to me. Do you have iptables running? If so, you'll need to allow rsh traffic through it.
Hear from you soon....