I can only assume that your users are on Windows. If that is the case there are a couple of things that will throw things off.

First be sure that your XML doesn't have any empty lines at the beginning. Also be sure that your namespaces match the version of Excel opening the files. He-Who-Must-Not-Be-Named has changed the namespaces AND functionality over the last three versions of SpreadSheetML.

Also check your xslt processor. I use the libxslt libraries through XML::LibXSLT and have to do some doctoring after the transform to get my namespaces correct.

Also, I think you touched on this at the last of your post, but saving the file to the file system and then opening is always a good step. But remember this, IE has a habit of overruling mime-type with file extension. In some cases past I have had the mime-type overruled in favor of the mime-type assoiciated with the file extension, and if you give it a file extension it doesn't have, it bails even if you gave it a mime type to use. So when you save the file:

What file extension to you give it?
Do you open by double-clicking or by the 'Open ...' menu?
Which version of excel do you or your users use?