Well, the plot thickens...
I investigated the "slowness" myself and discovered that the issue is very specific.
The user's application data directory is redirected to their shares, ie \\FILE-SERVER\user\Application Data
When the users have an xla file in \\FILE-SERVER\user\Application Data\Microsoft\Excel\XLSTART, Excel takes ages to open an Excel file. If that file isn't in there, Excel opens files immediately.
And the kicker...if Auto Protect is enabled on the file server with the xla file present, Excel takes ages top open files. If Auto Protect is disabled, Excel opens files immediately even with the xla file still there!
So SEP is doing something with the xla file when Excel opens!
I tried adding an exception for the xla extension and even the whole folder for the user, but the issue still remains. The trouble is, all the staff must definitely have this xla file present.
I can easily replicate the issue - how do we go about contacting Symantec support? Do we have to have support purchased?
Any other thoughts now?