GRE tunnel issue with packet size

[Lukasz_1]

Hello,

I am migrating old ASA to Palo Alto PA-440, one of the things i am trying to migrate is IPsec tunnel, that Ipsec tunnel carries only two remote hosts which are sources and destination for GRE endpoint on Cisco Switches. When i try to migrated it users complained about the unable to ssh to end hosts, when we tried to ping with the -df bit set and mtu set to 1368 it was working, but if we try to traceroute from end host to end hosts packets were not making over. My topology looks like the following:

Cisco_SWITCH(BGP, with GRE Tunnel) <---> PaloAlto PA-440 (IPsec tunnel, interesting traffic match tunnel source and destination) <--> Cisco ASA 5505 (IPsec Tunnel, intresting traffic tunnel source and destination) <--> Cisco_SWITCH(BGP, with the GRE TUnnel)

When ever users tries to ping or use https/http sites, ssh packets are lost, users not able to browse or ssh to other site of the tunnel. 

When i check the policy on PA i see bunhc of ips with destination or source of the GRE tunnel ends. Also i tried to lower MTU values on PA site (MTU on Tunnel site are alredy set to 1400) i went and lower it down MTU on ipsec tunnel on PA to 1368, but still not go. 

Anyone is doing similar to this set up, i want to add it that this is migration from ASA5505 to PA, when backout was executed to ASA everything is back to normal, NATttin is done to exclude those IPs of head end tunnels. In my understanding all packets would be encapsulated inside of GRE tunnel on Cisco Switches, correct? If that would be case why i see IPs pn policy that targetting the end tunnel? Any help would be very approciated it.