Update to the topic.

Microsoft really did not suggest a great deal of improvements except to use OPTION (Force Order), changing MAXDOP settings, running the query in DTA and implementing index suggestions and saying that little difference in CPU architecture can make a difference (latest 2.5Gz vs Old 2.8Gz)

Implementing an index suggestion from DTA tool on the biggest table did make a difference and the execution time has come down to 1min, however this does not explain why on the other server without this index it is still better.

We had taken a look at the histogram and did realize that sampling is very much different in both. Faster one has a sample of only .25% of the total rows whereas the slower one has sampled the total rows.

Hence we restored the backup again and did not update the stats and then ran the query, surprisingly it is exactly taking the same time as the old server which was faster !