It wasn't the statistics that fixed the issue, it was the query plan being invalidated and recompiled (ie. new plan).
From BOL:
http://msdn.microsoft.com/en-us/library/ms187348%28v=sql.105%29.aspx
Updating statistics ensures that queries compile with up-to-date statistics. However, updating statistics causes queries to recompile. We recommend not updating statistics too frequently because there is a performance tradeoff between improving query plans and the time it takes to recompile queries.
Also see