The krb5-1.1.1-16 errata upgrade breaks "rsh -f"'s credential forwarding. The fault is on the server side: an upgraded client (also running the upgraded KDC) can still correctly connect to an unupgraded host via rsh -f, with ticket forwarding working OK. Forwarding in general still works: telnet -f succeeds. Only the kerberised rsh (with or without "-x" session encryption) fails. This is rather high priority, as single-signon is the whole point of kerberos, and that functionality breaks over more than one hop in the upgraded packages.
Fixed in rsh, still hunting for it in rlogin.
*** Bug 17404 has been marked as a duplicate of this bug. ***
This should be fixed in krb5-1.1.1-25 and krb5-1.2.1-9 and later. Until Raw Hide gets refreshed, new packages can be grabbed from http://people.redhat.com/nalin/krb5/.