this focus on NATs seems to be an incomplete statement of the problem
a complete statement of the problem is quite difficult, especially given
that the problem can be viewed in many different ways (without any of
them being contradictory with the others), each of these views being
illuminating and therefore useful. RFC 2993 is one view;
http://www.cs.utk.edu/~moore/what-nats-break.html is another, and
there are some other quite illuminating views that haven't been published.
and we're still in the process of discovering the extent of the problem.
private addresses aren't a problem by themselves as long as people don't
want hosts with private addresses to exchange *any* traffic with the
global Internet and as long as people don't expect to run applications
on such hosts that interoperate with other applications on the Internet.
ALGs (which is what I assume you mean by firewalls) cause their own set
of problems, some of which are similar to those caused by NATs. the
fact that NATs, ALGs, and firewalls all are in wide use and that their
effects combine with one another makes it difficult to talk about any of
these in isolation regarding their effect on the network or on applications;
the fact that these functions often appear together in the same box also
adds to the confusion.
but just because ALGs and/or firewalls cause some of the same problems as
NATs does not mean that it's not useful to focus on the problems caused by
NATs. there is an important difference between deliberate harm to
interoperability done by firewalls in the name of security (or the illusion
of security, but I digress) and the accidental/unintentional harm to
interoperability that is done by NATs.