Performance degradation after rebuilding indexes
It's because when you rebuild indexes, you also necessarily rebuild the statistics on each index as it happens.  That means that SQL Server rebuilds internal "tables" of data about the distribution of data in your indexes themselves.  The distribution of data indicated by your statistics govern how the cost-based query optimizer chooses to create plans for your queries.

In essence, it means that SQL Server is probably executing your queries using a different plan than it did before because the distribution of your data changed.  

There's no simple fix to this.  It involves real detective work.  Start with SQL Server Profiler and get an idea of what queries are actually running in this job.  Analyze each query plan in detail and find out what parts of the query are taking the most time, and adjust your query, indexing scheme, or even your schema accordingly.