Maybe /etc/shadow has been corrupted somehow. I have never seen this happen but it's theoretically possible.

Instead of using single user mode, boot (for example from lilo) with the kernel command line
Code:
init=/bin/sh
This will bypass *everything* and dump you into a shell (beware, most things won't work)

Next, you need to remount the root fs read-write (as it will undoubtably be read-only at this point). Do something like

Code:
mount -n / -o remount,rw
This should make the root fs r/w. Assuming this works, try

Code:
touch /x; rm /x
which should work

Next, you can repair /etc/shadow. It's easiest to look at it using an editor (say, vi)

vi /etc/shadow

You'll see if it appears the correct structure (similar to passwd). If it doesn't seem structurally sound, copy /etc/shadow- over the top (this is a backup which gets made automatically)

Next reset root to having a blank password. Change the 2nd field of root's line in /etc/shadow to nothing, so the line looks something like
Code:
root::12092:0:99999:7:::

Although yours might look slightly different.

Exit the editor, run sync, then unmount the root fs

Code:
mount / -o remount,ro
Then hit ctrl-alt-del (ignore any messages which come up now, it's expected that there will be a lot of errors because the system isn't up running properly)

Now you should be able to login as root with no password. Then change the root
password back.

All this assumes your system uses shadow passwords (virtually no Linux system
made in the last 5 years doesn't by default)