I've just encountered this same problem after upgrading a RH 7.2 box to FC1
The problem was the password lock files (obviously) but also quite literally.
I did the following:
mv /etc/passwd.lock /etc/passwd.lock.bak
and then repeated it for:
after doing this, i could add and remove users again.