The Gestalt of Performance? Just curious...

Parameter sniffing is usually the cause of something like this. When you run the query as just a query, all the parameters are local, so SQL Server can look at them, sniff them, and determine an execution plan based on the values. As soon as you put parameters in a stored procedure, SQL Server assumes an unknown value in the parameter, correctly, and creates a different execution plan. In most cases, this works well. In some cases it doesn't. Then you get into using the common work-arounds, like setting the procedure parameters to local parameters inside the query after initiating the local parameter with a known value. This is basically the same as using the OPTIMIZE FOR query hint in SQL Server 2005/2008.

Do you have any conditional statements in your procedure? Do you alter any of the input paramaters? If you do, the optimizer give you an incorrect execution plan. The statement below may cause an incorrect execution plan.

create proc spTest @id int 
as 
select @id=id from someTable where someCol = someValue

SELECT * FROM someOtherTable WHERE someOtherCol=@id

You can compare the execution plans to see if there is any differences.

How many joins are involved? More than 4 joins in SQL server 2000 will cause the optimizer to give up, but that doesn't explain why the code works when you run the code outside the procedure.

Do you execute all the code from the procedure? I have seen cases when the compilation of the procedure took 20 seconds, but the execution of the statements took less than a second. It was caused by some complex statements and some "constants". When I replaced the constants with the values the compilation was also less then a second. I will try to add some pseudo code for you to consíder.

    CREATE PROC spTest2
    AS
    declare @x int, @y --"constant"
    SET @x=10
SET @y=20
    SELECT * from table1 t1 
    INNER JOIN table2 t2 ON t1.x=t2.x
        INNER JOIN table3 t3 ON t2.z=t3.z
WHERE t2.y IN (@x, @y) --replaced this with values and it worked

Personally I think it was really strange, but the procedure was recompiled for every execution.

Another culprit is the ARITHABORT setting which may be set differently for the stored proc and your SSMS session. more here