The server side of rsh is the rshd - is it enabled = find it in /etc/services and in /etc/inetd.conf?
If you don't have /etc/inetd.conf - check /etc/xinetd.conf (and any includedir directories it may be searching. Is rshd there?
Check your firewall - ipchains or iptables - is port 514 specifically enabled?
Check the man page for rshd as well :
http://www.mcsr.olemiss.edu/cgi-bin/man-cgi?rshd+1
Good luck,
Gary Allen