Index fragmentation is quite unlikely to cause sudden slow performance. Index fragmentation is in fact only a concern when you're doing large range scans from disk.

Now statistics, that's a lot more likely to be the problem. Try a stats update with fullscan (yes, it'll take a while) and see if that helps.