Stale stats or bad plan in cache to be honest.
The optimiser has no knowledge of fragmentation, so that won't change plans, usually when rebuild fixes query problems it's actually the stats update that fixed things
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