SharePoint - Microsoft Excel cannot access the file......

Question

We're getting the following error message when trying to open an Excel spreadsheet from SharePoint

We have:  

Confirmed the file is ok (if you move it to a local location it works).

Re-syncing the SharePoint library 

Opened the file from a SharePoint library on another computer - it works ok

Clearing the Office cache as advised here - https://social.technet.microsoft.com/Forums/ie/en-US/1e6a0e4f-a7be-4b3c-a564-21acb2c52186/office-documents-not-opening-from-sharepoint?forum=sharepointadminprevious

Any other ideas?

Thanks