You may need to check the network share to make sure that it's not read-only and look for the presence of the so-called 'owner files' which are hidden files with filenames starting with ~$ followed by the name of the Office document.
According to Microsoft*, these 'owner files' are created when an Office document is opened by a user. They are created in the same folder as the document and contain the user's logon name.
When you open a document that's already in use by another user, the Office program uses this file to determine the name of the user currently using the file. However, if the network share is read-only, the file wouldn't be created and you may get the locked for editing by another user error.
Office programs normally delete this file when you close a document but if the program was abnormally terminated, the file may stay behind.
You can try deleting any 'owner files' you find on the network share and see if that works.
Other people facing a similar problem can also try installing this hotfix or looking through this TechNet thread for alternative solutions.
*Owner File (Same Directory as Source File)
When a previously saved file is opened for editing, for printing, or for review, Word creates a temporary file that has a .doc file name extension. This file name extension begins with a tilde (~) that is followed by a dollar sign ($) that is followed by the remainder of the original file name. This temporary file holds the logon name of person who opens the file. This temporary file is called the "owner file."
When you try to open a file that is available on a network and that is already opened by someone else, this file supplies the user name for the following error message:
This file is already opened by user name. Would you like to make a copy of this file for your use?
Word may be unable to create an owner file. For example, Word cannot create an owner file when the document is on a read-only share. In this case, the error message changes to the following error message:
This file is already opened by another user. Would you like to make a copy of this file for your use?
Note Word automatically deletes this temporary file from memory when the original file is closed.
When you open a file by using the HTTP or FTP protocol, the file is first copied to the temp directory. Then, the file is opened from the temp directory.
When you open a file on a UNC share with Word 2007, the file is first copied to the temp directory. Then, the file is opened from the temp directory.