Exchange Servers and Firewalls

We recently had our firewall replaced because our old one was defective. The old one was configured by a company no longer in business. We have a Windows 2000 Server running Microsoft Exchange server for our dedicated domain. We have a high-speed modem that gives us a dynamic IP address and the firewall has a DHCP client resolving our internet connection round-the-clock.

Since installing the new firewall, our internet has been restored to all of the machines including the server and internal messages send and receive fine. Internet e-mail and messages sent outside our domain are currently not working. No settings have been changed on our server since the firewall crash, so is it something with our firewall set up, dns, etc?

Any help is greatly appreciated.