It depends on the NAT implementation. I've done 6in4 tunnels just fine through NAT. Its just that usually the crappy little routers that are typical of residential CPE have awful network stacks and NAT implementation.
Truth. That being the case, I'd stand by my original recommendations: If one has a router that has a decent NAT implementation, it's likely v6 capable, and might as well be used for terminating the tunnel. If it's a simple home router, trying to get a HE tunnel through its NAT reliably is likely to cause premature baldness.
Apple Airport Extreme does v6 tunnels, and works with HE tunnels as per these forums. That might be the easiest way to go for a home user who doesn't want to fiddle around with Hexago, wants an easy way to bring v6 to several machines, and has no desire to buy or learn how to configure a "business-class" router.