Rebuilding indexes also updates statistics. My guess is that your statistics weren't up to date and the query optimizer therefore did not use the index.

Regards,

Martin.