A SharePoint document library in some ways acts similar to a folder when storing documents on your local computer. For example, you can’t have two documents with the same name within a document library (or folder, if you are using folders). If you try to rename a document and give it the same name as another document in the library, you will be given this wonderful error (in SharePoint 2007):

[Server Error in ‘/’ Application. The specified name is already in use. A document cannot have the same name as another document or folder in this library or folder. Click your browser’s Back button, and type a new name.]
This makes perfect sense, unless the “existing file” really isn’t there. I recently ran into an issue where a user tried multiple times to upload a document (PEBKAC) and finally, they received the error that they couldn’t add the document with the current name because it already existed. Somehow, the document they were uploading and checking-in was removed from the database, but SharePoint thought it was still there. So, they couldn’t upload a document or rename a document with that same name.
When I tried to upload a document to the library, I received the error below that says the document (which wasn’t really there) was checked-out to the user that was uploading the document from before.

[Error. The {filename} is checked out or locked for editing by {username}]
Again, since the document really wasn’t there, it was a bit frustrating, but this last error did give me insight into how to resolve the issue. The fix in this case was simple enough. After opening the document library’s settings, I opened the Manage checked out files page (selected from the Permissions and Management column).

Since SharePoint did believe the document was still there, I am given the wonderful opportunity to “Take Ownership” of the checked-out document.

After selecting the checkbox next to the document and clicking the Take Ownership of Selection button, the document was then checked-out to me. I then was able to upload a document with the same name (the library had versioning turned on, so I selected for it to add another version).