Yes, you can atomically update each table. It was designed that way.
That doesn't mean that applications use the kernel API appropriately; for a long time libiptc didn't give you a great way to do atomic updates of more than one rule at a time.
Changing NAT rules is a weird one, because for radical changes you really want to kill all old connections. Figuring out which existing connections would be NATed differently and resetting them might be a nice twist if people were seeing problems here.