I know this may crazy as hell but try this:
Open notepad and copy and paste this into it:
save the file as:
Excel Network Fix.reg and then open that file. Should ask if you want to import it to the registry, click yes.
See if that fixes the issue.
Test it somewhere though!! I ain't held responsible for damage to your network
Is there some sort of sharing conflict or something?
Is there enough space on the drive the user is saving to?
Maybe reinstall Office? or just Excel?
Also check these out from Microsoft:
Q212147
KB313937
Another idea i found: