You don't specify exactly what version of Excel you are running. This is a known problem with certain versions of Excel. We had the problem, exactly as stated. It is not a network problem. It is not an NT problem. It is not a workstation problem.
It is a problem with Excel. The updating of a certain DLL resolves it. Apply the latest service patch for your version of Excel or upgrade to one of the newer office version should resolve it.
We were able to pinpoint the problem because we had different versions of excel and depending on the version, the person would or would not have the network saving issue.
Its been a fairly long while since I have seen or heard of this problem so I can't remember any more specifics.
-Wayne