Next time try just updating statistics.

You've given just about nothing to go on there, so it's impossible to say a cause. Fragmentation won't cause that kind of performance degradation, so it's not the fixing of fragmentation that solves the problem. Rebuilding an index also updates statitics causing cached plans to be invalidated. So it's likely either poor stats leading to bad plans, or a bad plan getting into cache which gets cleared out when the stats update invalidates it. No way to tell which though.

Can you at least identify the query(s) that are running slowly? Execution plans would be awesome too.