I am confused here. Web access and inbound emails are two separate issues. Are there problems with email delivery to your organization? Are users having problems getting to Domino web access portal? These are two separate services. I am not familiar with the specifics of Domino web access but can speak from general email and web access background.
Web access typically runs over port 80 (http) or 443 (https). So, your firewall must permit these services on the specified host IP address(es). The other part of this is that the public DNS record for the website name must point to the correct IP address. So, if you have changed from Verizon to ATT, then the IP address for the web access host has changed. The public DNS record will need to be changed accordingly. DNS replication may take up to 72 hours through the internet so it could take a couple of days for changes to propagate.
What I mentioned about DNS records above for web access also holds true for MX records. Replication can take a while. That is why it is a good idea to have multiple MX records with various weights so if one host is unreachable, the next host in the list may receive emails. This is true even if you have one host and are adding a second host and then shutting down the first host. You will first need to modify the A record for the mail host and then add the additional MX records to permit mail flow to the new host (that is if you have also opened port 25 – SMTP for the new IP address).
Can you provide more information about your new firewall config and what public DNS records show (you can munge the addresses to make them more private)?
In the IT trenches? So am I – read my IT-Trenches blog.