check your query plans - view estimated plans, not actual. I'd give best guess your proc is table scanning not using an index seek - index to suit.
( could also be parameter sniffing )
[font="Comic Sans MS"]The GrumpyOldDBA[/font]
www.grumpyolddba.co.uk
http://sqlblogcasts.com/blogs/grumpyolddba/