I noticed that updating statistics did not remove what I determined to be a bad query plan. I thought this was odd. I searched connect and found a bug submitted by Kimberly Tripp.
I thought a-ha! If she thinks it is a bug it is probably a bug. But it turns out that this is by design and the data has to change in order for the plan to change. While this makes sense it is different than previous versions.
The morale of the story is to think before recollecting stats. Did the data change? If not then don’t update stats. In order for stats to have an impact it means the data changed but did not hit the threshold for auto update stats to have run.
If you think the plan is bad for some reason then recompile or delete the plan handle.