rsh without password, New problem

Hi all,
Thanks all for having this group.
I am New to the world of Linux and networking. I request you
to help me in solving my problem.

I have 2 linux installed machines. Machine A and Machine B.
Basically i need to execute "rsh B -l root mkdir /root/sanny" command
from machine A.
And i need to use rsh only.

Senario 1:: I am able to connect succesfully from Machine A to Machine
B with { #rsh A } which asks for password. But when i issues a command
along with it it gives me an error. i.e when { #rsh A -l root date} i
get error as "pollrotocol failure in circuit setup".
Senario 2:: I am not able to login without command execution. i.e i am
not able to connect to the Machine A from Machine B with {#rsh B}
itself. It says "A.domain.com:Connect refused"

The below the following steps that i followed on these 2 machines.
1) Both machines have ALL : ALL in /etc/hosts.allow file and nothing in
/etc/hosts.deny file.
2) Both machines have rsh , rlogin, rexec enabled i.e in the file
/etc/xinetd.d/(rsh) (rlogin) (rexec) the disable is turned on from
disable=yes to disable=no.
3)Both the machines have ~/.rhosts file conents as "+ +" . (i also
tried with host.domain.com names).
4)Both the machines had /etc/hosts.equiv files with B.domain.com and
A.domain.com names respectively in Machine A and in Machine B
5)Both the machines were restarted after saving the changes.

Thanks in advance
Sanny