Too small for rebuilding to matter?

It's unlikely that rebuilding the index fixed the problem. It's far more likely that the statistics update which the rebuild performs fixed your problem. Consider adding some manual statistics updates on the tables you identified.