Could well be that the stats that the query depends on are column stats, not index stats. REbuilding an index only updates the stats associated with that index (and invalidates any plans that use it)
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