I too have this issue. I run IT for a small company. Several users with Verizon. When in most WiFi networks, sync with our exchnage 2007 server works fine. However, ios users on 3g and LTE networks receive the, "Cannot get mail. The connection to the server failed." message. I have a Gmail and a Hotmail account on my iPhone5 that work fine accross all networks.
An Ipad2 user is having the same issue. The iPad is WiFi only, but, since they are using the Verizon Wireless MiFi Hotspot to connect LTE on the job site, same "Cannot Get Mail" message pops up.