If the rules pass the traffic, and outbound NAT is set to NAT them out, it should work. Though there is not enough detail to say for sure. Make sure the rules pass all traffic, not only TCP.
Some other things to check:
Try to ping the firewall (their gateway), if they can't, then rules are probably to blame
Try to ping an Internet host by hostname, such as www.google.com, if it can't translate the name to an IP address, check your DNS
Try to ping an Internet host by IP address, such as 8.8.8.8, if the other parts work but that does not, it's likely outbound NAT