Of course it's going to take some time... your sproc has four relatively large SELECTS and they ALL must be recompiled even if only one is going to be used...

The other thing you may be running into is a thing that happens with variables (I'll be damned if I can remember what they call it)... basically, you need to assign each input variable to an explicitly named variable... can greatly improve the speed if the problem is occuring (what the heck do they call that problem? Variable something or other...)

Believe it or not, another thing you can try is adding the WITH RECOMPILE option to a stored procedure... sometimes it helps even on something like this.