If I try to rdate from a redhat 6 computer either from redhat 6 or Sun Solaris I get a: [dol@flash ~]$ rdate localhost rdate: No such file or directory or from solaris: tulpan> rdate flash rdate: read: Error 0 rdate sets the time normally from a solaris machine, so the problem may lay outside rdate itself. But this is soo obvious, maybe something here is screwed.
Check /etc/inetd.conf for the line time stream tcp nowait root internal For weird reasons, Red Hat has often shipped /etc/inetd.conf with a buggy time service configuration. Please reopen this bug if the above is not your problem.