There are a couple of things that you could look into. Ensure that the devices are not using an older version of IOS that doesn't support NAT-T. Check to see if the devices using NAT-t are actually behind a NATing device.Check if you have not blocked 4500 udp.
We have configured the outside and inside Interface with official ipv6 adresses, set a default route on outside Interface to our router, we also have definied a rule , which also gets hits, to permit tcp from inside Interface to any6.
In Syslog I also se...