are you using CBO?
If so make sure you are refreshing stale statistics