We had the exactly same problem with an application I use to work with. Customers didn't know what was going on, and felt things were taking to long to complete.

We cheated and simply used Javascript to open another window, and show an animated gif. There was no progress bar shown, no kind of attempt to show percentage done at all, it was a pure con. However most people were fooled, and thought it was much nicer, and even that the processes were running quicker - which they were not.

Useability Guru Jakob Nielsen has a lot to say about this kind of feedback at Use IT, and even though it's hard to do, it's not an unreasonable request.

My humble virtual 2p