The answer to every problem is to rebuild statistics. (And never use stored procedures. It's just a shitty API layer in the worst language imaginable, sitting outside of source control. If you need an API layer, write it in a real language, ideally the one you're already using.)