One solution is to use krb5-telnet server instead of telnet server.
Open service configuration window. Go to On Demand Services tab. Remove the checkmark, if any, beside ‘telnet’. Put checkmark beside ‘krb5-telnet’. Save the settings. Then, switch to Background Services tab and select xinetd and restart it.
I hope it’ll fix your problem.