I guess my first step would be to run a port scan on the server.
Second, I would check all my non-user id's, i.e.: htdig, mysql, nfs, etc..., and make sure they don't have a shell script applied against their user id's .
Third, I would check my password policy to ensure that your users can't use simple dictionary names for passwords.
Fourth, I would set up port sentry to keep an eye open for any weird activity, and if you have a spare linux server around and a couple of nic cards, I would activate tcpdump and monitor activity coming into your network for a couple of days (hopefully you've got the space).
Finally, shut down non-required services and try to get your users to use ssh and sftp when/if they connect to the server. That way you can get rid of telnet which, as you likely know, send passwords and userid in the clear.