yes apply the nat out side on the tunnel interface not the physical outbound interface
not sure exactly what the NAT setup is but the logic to have the traffic going through the gre tunnel nated you need to apply the nat out side on the tunnel interface
i am assuming you have the routing configured to route the traffic for the nated IPs over the tunnel on both sides !
hope this help
if helpful rate