Slow update commands only on newly added data? Data gets read in every quarter into this table. Then after it is read in, certain fields get updated through an update command. The updates run really fast on the previous quarter's data, but when it gets to the new data it takes a long time.

We solved the problem by rebuilding the primary key after data is read in, and then running the update commands. This makes it just as fast as previous quarters but the rebuild can take a long time.

When I rebuild the indexes,  we started using a fill factor but that did not help the cause. 

Is there anything else I should consider?
It is taking a long time because of out-of-date statistics. You've added a lot of rows to the table, so the statistics are not good now. Rebuilding the primary key seems to resolve the performance issue because you get updated statistics when you rebuild an index. But rebuilding an index is an expensive way to just get updated statistics.

Run UPDATE STATISTICS WITH FULLSCAN on the primary key, or consider a sampling. If the table has millions of rows in it, perhaps a 30 percent sampling would do the trick.