SQL Server query performance affected by rebuilding an un-fragmented index
It sounds like the rebuild of the index is a red herring, especially given it was non-clustered. The rebuild is more likely to be invalidating a bad query plan in cache, and on re-run the good query plan is generated and used again.

Captue the query plan when the performance is bad and then after the rebuild and compare them, I suspect you will see a different plan.

That would be my first step - e.g. demonstrate what changes to the plan due to the index rebuild, or prove there is no change on the plan.