It could just be that your statistics were out of date on the old tables and the new tables, with more up to date statistics, are generating new execution plans. I'd suggest running the query against the old and new tables, capture the execution plans, and compare them. Specifically, look to the estimated number of rows and executions for the operations.

Also, check the foreign key constraints on the old tables. Maybe they were created with NOCHECK. That could also lead to differences in the plans.

In general, in order to understand the choices made by the optimizer, you need to look at the execution plans, not just blindly rebuilding indexes.