The problem was unlikely to be due to a fragmented index, while fragmentation can slow queries, it's not usually that much. Most likely what fixed the problem was the statistics update that also happens when you rebuild an index.
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability