What can cause statistics to get out of line? 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?
I'll guide you to an answer to an older question. Please read the comments, too, they are very valuable.

In short, MSDN says:

"Insert Operations Occur on Ascending or Descending Key Columns Statistics on ascending or descending key columns, such as IDENTITY or real-time timestamp columns, might require more frequent statistics updates than the query optimizer performs. Insert operations append new values to ascending or descending columns. The number of rows added might be too small to trigger a statistics update. If statistics are not up-to-date and queries select from the most recently added rows, the current statistics will not have cardinality estimates for these new values. This can result in inaccurate cardinality estimates and slow query performance.

For example, a query that selects from the most recent sales order dates will have inaccurate cardinality estimates if the statistics are not updated to include cardinality estimates for the most recent sales order dates.

After Maintenance Operations Consider updating statistics after performing maintenance procedures that change the distribution of data, such as truncating a table or performing a bulk insert of a large percentage of the rows. This can avoid future delays in query processing while queries wait for automatic statistics updates."

So you would benefit from searching for statistics that were not updated recently.