Apple Mail issues with Uverse, new Motorola modem.

We just changed offices and AT&T came over to hook up our internet service, upgrading our Uverse modem to a Motorola NVG510 (from an older 2Wire unit). Ever since installation we have experienced intermittent email issues with our Macs:

1. On two Macbook Pros (mine running Mavericks 10.9.4, the other running ML), our email accounts go offline periodically, then go back online on their own. If I click on the offline symbol I get the message: "The server returned the error: The connection to the server “p02-imap.mail.me.com” on port 993 timed out." -- or similar, depending on the account. If I quit and relaunch Mail or just wait a few minutes, the problem is resolved. I have several email accounts (iCloud, Gmail, and business accounts through other hosts) and they all experience this behavior. FWIW, all accounts function normally at home (Time Warner Cable).

2. Another MBP running 10.8 ML is experiencing issues with Verizon Fios email accounts in Mail. They work fine at home where he has Fios, but once in the office those two POP accounts return connection errors on their ports -- 465 and 995 (for incoming/outgoing). He can check the accounts via the web just fine. Oddly enough, if he connects to an open Netgear wifi network in the building, those emails work fine (??)

I thought the solution for #2 would be port-forwarding, so I tried that on the router but nothing changed (t's a rather confusing interface and though I followed instructions I may still have done it incorrectly). I'm baffled as to what to do about issue #1 though.

TIA,
JVK