On the Cisco's they really need to tell the tunnel that it needs NAT-T, to my limited Cisco knowledge.
Next to that lowering the MTU will also lower the MSS and should NOT be done, when you want to do anything get the MSS adjust going, never mess with the MTU, it just works counterproductive.
The MSS value is the actual number of bytes a packet can transfer, when you use and a IP-Sec tunnel with a header of 64 or more bytes and on top of that another GRE tunnel header of 32 bytes, you actually reduced the actual MSS with another 100 bytes.
Once the tunnel is up and running, test with tcpoptimiser, a freeware program what the actual MTU is they say can be used through the tunnel, reduce that by 40 (20 IP header + 20 TCP header) and use that as the MSS value.
For a very good document on MTU, MSS and fragmentation is this:
http://www.cisco.com/c/en/us/support/docs/ip/generic-routing-encapsulation-gre/25885-pmtud-ipfrag.ht...
Regards, Maarten