I have the same problem at my work. I want to automate and speed up a lot of the reporting my coworkers do by moving the processing over to one of our Linux servers, but Excel is always a problem. Some of our people actually see Excel as a platform in itself.
It's become kind of a joke among some of us there. "Excel would make a great Operating System if only it had a decent spreadsheet."
Some of our macros can take upwards of twenty minutes to run.
I suppose they could use OpenOffice-server, and I've considered playing around with it, but it seems like too much unnecessary overhead. Right now I think I'm gonna give JExcelAPI a whirl as soon as I get a break in between projects.