Patching related info from the Excel blog:
http://blogs.technet.com/b/the_microsoft_excel_support_team_blog/archive/2011/09/29/office-file-validation-causes-slow-opening-of-excel-files-from-network.aspx
http://blogs.technet.com/b/the_microsoft_excel_support_team_blog/archive/2011/09/28/links-in-excel-are-broken-after-applying-security-update-ms11-072.aspx
If you are seeing that second one, can you call into Microsoft? They need repros in order to fix things and when they don't have repros, they can't fix.
Also recently saw an issue where Excel files would not save to a network share in 1997-2003 compatibility mode. Came down to permissions. All folders must have "Modify" rights in order for Office 1997-2003 compatible files to save. Having "Write" permissions is no longer sufficient. This just started within the last month.