I have experienced this exact problem and found, on the users machine, one of the libraries I depended on was marked as "MISSING" in the references dialog. In that case it was some office font library that was available in my version of Office 2007, but not on the client desktop.
The error you get is a complete red herring (as pointed out by divo).
Fortunately I wasn't using anything from the library, so I was able to remove it from the XLA references entirely. I guess, an extension of divo' suggested best practice would be for testing to check the XLA on all the target Office versions (not a bad idea in any case).