Even though stats are updated "every week", it could still be a stats problem. It could also be that the data finally reached a "tipping point" and caused code that doesn't necessarily scale well (despite previous "good performance") to choose a less than optimal plan.
--Jeff Moden
Change is inevitable... Change for the better is not.