resolvi isso.
Mas infelizmente não descubro por que isso acontece.
Quando eu corro no hostA:
# getcap /bin/rsh
Eles não retornam nada.
No hostB eles retornam:
getcap /bin/rsh
/bin/rsh = cap_net_bind_service+ep
Eu apenas removi o pacote e reinstalei usando yum
e eles receberam as permissões.
Mas por que isso ocorre no começo? O que está faltando na primeira vez que foi instalado? Estranho.