Why does the Query Execution plans differes from prod to lower environment?

Hi there,
    We are facing some trouble in executing few queries which takes more time(1:30) in Production server but whereas in lower environment(staging DB) its takes just 7 seconds to bring 10 records of data. To test this issue , I have taken the copy of Production DB and restored it in the same lower environment where the staging DB is located. When i tested the query against the production copy, again it was taking more or less same time 01:25 sec to execute.

1)I observed that that the execution plans is different from both the databases . Not sure why it is ?

2)I have tried updating the stats and rebuild the indices. Again the same time to execute and no change in execution plan.

3) Can somebody shed some lights on this issue? Is this because of the job which i configured few months back to perform rebuild indexed and Statistics update?

thanks
Deepak