The usual cause is that the master lock file, `!!!SuperLock!!!' has been left in the lock directory somehow. Delete it.
Mark Meuer <meuer@geom.umn.edu> says that NeXT NFS has a bug where an exclusive create succeeds but returns an error status. This can cause the same problem. Since Emacs's file locking doesn't work over NFS anyway, the best solution is to recompile Emacs with CLASH_DETECTION undefined.