No, the problem is that we really do need more address space. IP addresses include identification information and network topology information. We really do have almost that many computers, and almost that complex of topology.
Forcing the holders of large legacy allocations to give them up would hurt more than moving to IPv6, and it'd only get us a few more years of IPv4 growth. Opening up the class-E space would also hurt more than moving to IPv6, and still only give us a few more years.
NAT effectively adds 16 more bits to the address, but does so on a per-connection basis, not a per-node basis. It requires the network to be stateful, instead of just passing packets while the end hosts carry all the state. (This means that the end hosts can't just route around problems.) NAT is messy, but it happens to work because it can steal some bits of TCP or UDP to make up for not having enough in the IP header.
IPv6 adds way more address space than anyone can think of a use for. So it can encode a lot of information about the node's position in the network, plus keep an address unique for (practically) ever.