You seem to be mixing things up a bit.
named is the BIND DNS daemon.
telnet has nothing to do with named directly.
However, if you have the users' workstations using the server running named as their resolver then the telnet may time out when named is hung because their DNS query is timing out. If that is your issue then they should be able to telnet in with the IP address instead of the hostname.
Are the users trying to telnet into the server that has named or to other servers?
Why were you rebooting? If named was having an issue you should be able to try "service named status" before the boot and even "ps -ef |grep named".
Is this something that was working and suddenly quit or some new setup?
Have you reviewed your /var/log/messages log?
Have you tried enabling named tracing and reviewed the trace log?