I ran into a similar problem with a pix firewall and the outcome was that the data guy had to make modifications to the default pix "fix up" protocols in the firewall. Also make sure you have the remote gateway in your IP sets programmed correctly.