Ah, rsh... Our promiscuous, red-headed stepchild. Not really recommended, but still popular.
Are you tring to rsh over as root? This is disabled by default. Use the chuser or "smit user" to change this.
Also, are you sure that you setup the .rhosts correctly? When you log in using telnet or secure shell from one system to the other, how is the remote server resolving your IP? Type in "who" to check this out.
Where are you defining your hostnames? DNS, /etc/hosts file, both? You might want to make sure your /etc/resolv.conf file and netsvc.conf file look okay.
Is rsh defined in /etc/inetd.conf and is inetd running?
Has /etc/services been modified? There should be a "shell" entry.
Typically, rsh issues are because of hostname resolution and not /etc/inetd.conf or /etc/services, but I thought I'd mention them anyways.