It seems that latest glib-2.1.90 (rcmd ?) allocates local port above 1024 to clients like rlogin or rsh, which causes authentication to fail in in.rshd and in.rlogind, because these servers check that client's source port is in the range 512-1023. (do a strace /usr/bin/rsh remote_host cmd and search the socket that binds on port 514 for example).
I have been trying all day to figure out why rshd is not working! I have the same identical problem.