doesn't this require the NAT to use the same inside<->outside
address binding for the connection between the client and the KDC as
for the connection between the client and the application server?
e.g. it seems like the NAT could easily change address bindings
during the lifetime of a ticket.
True. However, the same problem applies without NAT if the client
changes address bindings,
granted, but how often do clients change address bindings in practice?
so I wouldn't say this is really a NAT-related problem.
of course it's a NAT-related problem, in the sense that if you
have a NAT box and want to use Kerberos you are highly likely
to observe the problem.
for almost every kind of harm that NATs do to applications you can
find some other means of causing the same problem. but just because
the problem can be caused by other things doesn't mean it's not
related to NATs.