Sorry but an update of the statistics is necessary as a rebuild index will not update the statistics on non indexed columns.

Andrew