May be a simple solution......
RegMon for Windows
http://technet.microsoft.com/en-us/sysinternals/bb896652.aspxFileMon for Windows
http://technet.microsoft.com/en-us/sysinternals/bb896642.aspxSet the filter at the top to Include "excel.exe", to highlight "access denied", and then try and recreate the errors by launching the application..........Then go to these apps, and look for the red, and it will tell you where the permissions are shot. Open up those areas for "Users" and then test.....
Or even use the new and improved utility form Sysinternals, that contains them both....
Process Monitor v2.03
http://technet.microsoft.com/en-us/sysinternals/bb896645.aspxSee if you can find any denials when working with Excel and this addin....