There are many factors that could affect performance.
Without more information, it will be really hard to answer.
Can you post your code?
The first thing that you need to do is identify what statement within your stored procedure is causing you the most problems. You can do this by looking at the execution plan in Query Analyzer (SQL 2000) or SQL Server Management Studio (SQL 2005+).
If you are doing index scans or table scans then you will probably need to add indexes to the table in question. This can include adding indexes to the temp table.
Instead of using a Temp Table you can try simply selecting directly from the temp table, unless there is a reason that you need the temp table. You can look into Common Table Expressions as a possible other option to a temp table.