Activesync issues after DNS update

-For two weeks, since we updated DNS records for our website(from an A record to a CNAME), we have seen intermittent issues with Activesync devices on the Verizon Wireless network – Android and iPhone.
-Errors have ranged from Certificate errors, server connection errors and general synch failures.
-We are not seeing these errors on any devices except for Verizon-- devices on T Mobile, ATT and Sprint have been unaffected.
-To get around the certificate errors, we tried sideloading the certificates on the Androids, but this only worked temporarily.
-The same Verizon phone that is unable to connect to activesync as a phone, is able to act as a hotspot for another activesync device to connect successfully.
-The errors are intermittent. Devices can successfully connect at times, but eventually experience an error when synching or sending mail.
-Via several traces involving our internet provider and Verizon, we are able to see where the traffic attempts to pass through the firewall and then is re-routed back outside to our website host. Both our provider and Verizon are able to see the traffic handed off to us internally, however we never saw the handoff to the ISA server or routed back out via the firewall.
-To eliminate our ISA server as a roadblock we setup a second instance of Activesync with a different server name, which bypassed ISA. This worked well initially for about a day, but has since started to exhibit the same intermittent connectivity issues.
-Our activesync server IP internally and externally is routed through the firewall so access from the inside should be the same as from the outside.
-Our internet provider has confirmed that they see no issues or packet loss via Verizon when attempting to connect to us, they see the hand off.
-we are using checkpoint firewall r75.20, ISA, and Exchange 2007.