Sure, but the difference is that it's now both a plausible moment to go MITM (because they got that key), and furthermore the hypothetical attacker now has good

Sure, but the difference is that it's now both a plausible moment to go MITM (because they got that key), and furthermore the hypothetical attacker now has good reason to believe users won't be scared by a host-key-change warning, and the hypothetical attacker would know this opportunity exists for a large set of users simultaneously. If some malicious network operator were to try and exploit users, now would be a good moment - they'd likely catch many more people in the time it takes to be discovered than on an average day. The MITM-at-the-start risk is of course real, but I think this new everyone -restarts-simultaneously risk is qualitatively different enough to be worth at least considering.