Can't restore root password

Can't restore root password

I have to start with the reason for all that mess…
Trying to set up Empathy, Ubuntu asked me to unlock the key ring Login.
But I was unable, because neither my Ubuntu root password (which is my
login password for my account as well) nor other passwords I'm using
worked.
Dissatisfied, I opened Passwords and Keys and deleted a Keyring named
Anmelden (German for login).
Actually, I have the following keyrings configured:

I know the passwords for the first two Passwords Login and Default but not
for Gnome2 Key Storage.
Presumable because I deleted one keyring, I can't access root anymore; No
password is accepted.
Further I can't change it via the recovery mode (as e. g. described here):
root@toshi:~# passwd
Enter new UNIX password:
Retype new UNIX password:
passwd: Authentication token manipulation error
passwd: password unchanged
Does anyone have an idea?