With only a few minutes thought on the subject, it seems like Congress could explicitly amend the APA to state that the interpretation in Chevron is correct.

They might not do that, but from my initial non-expert read of today's opinion, the Court only looked to the APA, not the Constitution in generating its ruling.