I would recommend changing NAT traversal from auto to manual. Put in the public IP that it will use to communicate. Then choose a port that it should use. I generally like to use ports that are easily recognizable like 31313 or 42424, you get the idea. Then on the Palo Alto create a port forward for the UDP port you've chosen to always be sent to the MX.
When the manual NAT traversal is set, dashboard will tell all of the spokes to communicate with the hub on the IP and port. If the Palo Alto is changing the ports (and causing the unfriendly NAT) it will break the UDP hole punch and will prevent the VPN tunnel from forming. The port forward will make sure that the spokes are always able to reach the hub.
If the tunnels still don't form then I recommend taking a packet capture of the internet interface on the hub and the spoke. Is there back and forth traffic between the two? Or is there only traffic going one way? If it's one way there is something blocking the traffic. If you have very strict firewall rules then I recommend that the rules be built around the UDP port instead of the IP of the spokes.
An old post of mine has some KB links for more details on troubleshooting AutoVPN.