resetting the root password also doesn't work.
That doesn't make very much sense. Suggestion, in addition to what rawthey and cracauer already said: Start in single user. Make a copy of /etc/passwd and master.passwd. Write down the timestamp on those two files. Then use the passwd command to change root's password. You should see that the timestamp on master.passwd changes. And if you compare the before and after versions of the file, you should see a difference in the line for root.
My suspicion is that the problem is not the password, but something else makes logins impossible. To find out what that is, it would be nice if you could tell us more details than "doesn't work". What exactly happens when you try to log in as root, or as another user? Does it say "Login incorrect", and immediately go back to a login prompt? What happens if you try to log in via ssh (assuming the system is on the network)? If you go into single-user mode and inspect the auth and system logs, what do you see?
There are zillions of reasons why logging in might be broken. They could be as simple as the login shell of these users being set to a non-existing executable: If the are set to execute /usr/local/bin/foobar_sh, but such a program doesn't exist, then they won't be able to log in. Perhaps they are using a shell that has become broken? Perhaps they have a login script (such as .cshrc or .profile) that breaks immediately? I can make login impossible by creating a .profile file that simply has the word "logout" in it.
Here is another debugging suggestion: In single user mode, create a new user. Give it a super-simple password (like password) and an easy-to-type username (like user). Make sure they have a valid home directory with correct permissions, but then make sure that home directory is empty. Give them a boring standard shell, such as /bin/sh. Make sure files such as /.cshrc and /.profile and /etc/*shrc and /etc/*login are harmless (perhaps temporarily move them). Then reboot to normal mode, and try to log in as that user. It should at least function, and give a very boring result.
EDIT: And disconnect the network while you have a user with such an insecure password, and remember to delete the user when you're done.