The Generic Route Encapsulation (GRE) protocol is used in conjunction with PPTP. Data or payload that is going to pass through the tunnel is given a Point-to-Point Protocol (PPP) header and then placed inside a GRE packet. The GRE packet carries the data between the two tunnel endpoints. After the GRE packet has arrived at the final destination (the endpoint of the tunnel), it is discarded and the encapsulated packet is then transmitted to its final destination.
So I'd check that your NAT device allows TCP port 1723 and GRE (IP protocol 47)