DMVPN with NAT
It looks like Cisco has been fixing NAT issues with DMVPN. They fixed the NAT issue for spokes talking to the hub using NAT traversal. This is the same method that VPN clients use. It uses UDP port 4500 to send the IPSec traffic instead of IP protocol 50 (ESP) and IP protocol 51 (AH).