Sounds like someone's a little lax in their security policies.
Sounds like whoever is getting in is able to use the 'root' account. Start by changing the password to the 'root' account. Make this something not easy to guess. Actually, you should make it something impossible to guess. I would write down random characters, including symbols such as !, $, etc., and then change the password to that. Make it very long (at least 10 characters), and put it in a safe place, then destroy it when (or if) you memorize it.
Next, if you're using telnet to access the system, stop! Anyone can observe what you are doing, including entry of passwords. Use SSH. There is no reason why anyone should need to use Telnet, since there are lots of good SSH clients available, even if you are using Windows ('putty' is a good one, and it's free).
Next, check your sshd_config file. Check the following:
PermitEmptyPasswords no
PermitRootLogin no
NEVER EVER allow someone to directly login as root remotely.
It sounds like someone obviously knows one of your usernames and passwords. At a minimum, you should change the passwords to your user accounts. For extra measure, I would change the usernames as well. Make sure they all have passwords, and they should be passwords that are not easy to guess. Don't be shy about imposing standards on passwords for your users.
Also, make sure they don't have something running on your system that can observe these changes and report these changes to whomever is doing this. You could do all of this and it would all be for not. If you're not sure if something is a legit process, do a 'ps -ef' command and post it here. Someone here should be able to tell if a process if bogus. If something isn't legit, kill it ('kill -9 <processnumber>').
Hope this helps.