To get rsh working you should all of these:
- allow the remote computer to access the rsh server (see /etc/hosts.allow and your firewall)
- make the rsh daemon usable (usually in /etc/inetd.conf there is a line about "shell" service)
- put a "IN A" and a "IN PTR" and record in the DNS specifying the computer which access your server (if your remote machine cannot be accessed as hostname.domain.net you will not be able to use rshd from that machine)
- tell the server who is using remote shell from that address (hostname.domain.net) in "/etc/hosts.equiv"
- now try again