Just wanted to update you all on this issue as it has been resolved (yeah!!!)

The problem got solved when I changed the statistics generation procedure to compute stats instead of estimate. All queries are superfast now.