The tsclient/rdesktop pair is installed and works properly on four of my EL6.2 systems.
Whenever something odd like you are descibing happens, I immediately suspect that SELinux is blocking some action, but I see you have already looked into that. If there are no errors in the various logs, then a problem is very hard to track down.
I have seen SELinux block an action even in permissive mode, but not report an audit flag. Those are very hard to track down and usually turn out to be something stupid like the read of a file was allowed, but reading the directory it was in was not allowed.
If you suspect a silent SELinux blockage, then reboot the system, stop at the grub menu, append "selinux=0" to the kernel command line and continue the boot. After the boot is complete, then retest the failing action.