Ok - so RESTORE the DB again - the slow one - onto the production server.

Do this:

Code:
exec sp_recompile SprocName
Then see if it runs "fast" on the first run.

If we changed the behavior of "first run" vs "subsequent" runs with this then we know that this SPROC falls prey to cached data access plans.