Slow update commands only on newly added data?
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.