I applied patch 108993-65 on two servers (5.8) and now I am unable to rcp to either machine. Getting "permission denied".
verify that .rhosts and hosts.equiv files did not get removed. Also verify your rohst pam module is still there.
pam.conf
rlogin auth sufficient pam_rhosts_auth.so.1
Those files are still in place and the rlogin line in the pam.conf file is there. 
Next try to truss the rlogin process and snoop port 513.