I have had many users experiencing issues of their emails being bounced back by other SPAM filters. The only thing that has changed on our network is the installation of the BBNA. Did I miss an important step in the installation?

Please add an interface binding rule for SMTP traffic so that both the outgoing and incoming traffic just stick to the single interface from the ISP that is allowing your email traffic. Try adding an interface bind rule for TCP port 25 (SMTP) traffic so that all the port 25 traffic sticks to that interface.