This is normal behavior. Have them right click on the document and select
Check Out before they try to open it for Edit.

We had the same problem, even when a document was checked out. It
turned out
that for us, the solution was to enable both Basic and Integrated
Authentication on the server.
(We had been using Basic--no problem, switched to Integrated--
problem, enabled both--
problem solved.)