/etc/xinetd.d/rexec starts /usr/sbin/in.rlogind instead of /usr/sbin/in.rexecd. rexec didn't work until I changed to in.rexecd.
Already fixed in Rawhide.
The version is rsh-server-0.17-2.4