Use query analyzer to see what execution plan is being used when executing these procs against the new database.
If it uses scans instead of seeks it may be that your statistics are out of date. You can examine that by using
DBCC SHOW_STATISTICS or STATS_DATE
Principal Consultant and Trainer