Peter:

Are you talking about users RDP'ing into a Terminal Server?

Each user has to have a licensed install of Excel on their Terminal Server user profile, or you could switch to Open Office