Issue Saving Microsoft Excel file on Network Share

So, I have an interesting issue that I cannot solve.

I have a Microsoft Excel 2010 file created by User A. User A has full permissions to the file. User A has created the document and saved it onto a network share folder. User B also has Microsoft Excel 2010 and can access the network share and can access the Excel file. User B also has full permissions to this file. User B should be able to Read, Write, Execute, etc., with the file. However, when User B attempts to make changes to the Excel file and save the changes to the network share, the user receives an error message reading, "Access Denied. Contact your Administrator."

Initially, we suspected that this was a simple permissions issue. Not the case. Looking further into the problem, I have since copied the entire Excel file into a completely new Excel file, saved the file to the Desktop and then moved the file into the network share location. User B still cannot modify the file and save it. I have renamed the computer to a completely different name and re-added the PC to our domain. Problem still persists.

At this point I'm thinking perhaps the issue lies somewhere within the registry. Rather than try and hunt down the problem, I simply reimage a new hard drive for the user, copy user files, etc., and add the computer to our domain. The problem still persists.

Recently, I have discovered that the problem occurs on other computers as well but only on computers with Microsoft Office 2010. Computers that still have Microsoft Office 2003 installed on them, User B can open the Excel file the user can perform changes and save the changes without issue. I can't understand why.

If I have User A login to User B's computer, User A can open the Excel file and make changes without issue. Several other users who also have full permissions to this file can open the file and make modifications without issue as well. It's only User B that experiences a problem with this file. At this point, I feel like I have ruled out a registry problem unless the registry issue lies somewhere within HKCU. Also, it's not limited to just Excel files. Word Documents and PowerPoint Presentations give the same, "Access Denied. Contact your Administrator" error message.

Does anyone have any idea what I could be missing here with this issue. I hope I have provided enough information. Thanks for any forthcoming replies.

No one?