I've just worked through a problem at a clients site which it turned out was caused by the statistics being wrong which caused the Optimizer to time out. Running
exec sp_updatestats fixed the problem and all is now good.
What I am a bit confused about now is how did the statistics get out of line in the first place?
The database has both auto_create_stats and auto_update_stats switched on. So SQL Server should have kept the statistics up to date without any intervention.
So why did it fail in this instance?
This client had recently upgraded their database server. They handled it themselves, so I'm not exactly sure what procedure they went through, but I can't imagine it was anything more complicated than backing the database up on the old server and restoring it on the new one. Could this have caused the glitch somehow?