Sounds odd, but this also looks odd:
This morning I tried to login as root in fedora machine it throws:
sh-3.00 # passwd root
Two points: first of all, to be able to run 'passwd', you need to be logged in already. So if you were able to run it, you actually had logged in (and to be able to passwd root's password, you need to be root or have loose sudo rights). Second point: there's a #
after the sh prompt, which (to me at least) looks like you are
logged in as root. Now am I right, or is there something odd going on there too? The rest of the thing surely does look odd..
You haven't tried to clone the root user, or make another user have root ID (0) - because such things, when failing, could cause something like this. Read passwd trough and first of all make sure there is no other ID 0 user there..
If you can't figure out what it is, or suspect there's a possibility somebody got in and is causing that, a clean overwrting reinstallation of your OS is the way to go, to be fairly sure.
I'm not sure if that's a valid entry..the exclamation marks (!) don't usually belong there. Added to a password field, for example, effectively cause the password to be "unreadable", thus locking the account (but still it should be there, just not let you in). Maybe you could try clearing the password field (and maybe go trough the other fields and see that their information is correct, or at least looks correct) and see if it zeros the password information. But if you can access the shadow file, you're logged in as root or have your system pretty well wrecked up.