>Figuring out which existing connections would be NATed differently and resetting them might be a nice twist
I do not think you can actually solve this "twist". The fact that NFCT mappings - and thus TCP tuples - do not change when the nat table is changed could be considered a feature in itself. Sort of like an RCU for tuples.