Exchange Server not receiving emails from Gmail accounts

I have been alerted that emails from users with Gmail accounts are not getting through to our users. We are running Exchange Server 2003 SP2.
I researched the problem here on EE, and found a long, elaborate discussion about this exact problem (ID #23302358). The resolution was that they created a new rule in their firewall to allow all outbound traffic. As quoted in the answer: "Adding a rule that allowed ALL traffic out which started at our mail server, everything seemed to work."
As we seem to be having a similar problem, I wanted to try this solution, but don't want to create a rule in our PIX that is not correct. We have a Cisco Pix 506e. There seems to be a rule already in there that is allowing all "IP" traffic outbound, but not TCP traffic. So do I need to make a rule to allow all TCP traffic going out, or should it be something else?
Any advice would be appreciated, but if you can answer, please be very specific about how the rule should be created. I'm always a bit nervous about our firewall. :-)
Thanks!