I use Ola Hallengren's maintenance solution, so stats are being updated nightly based on threshold.

The query uses a better plan after rebuilding the index, but could it possibly be bad stats on another table that the query uses, that's not related to the index?