Doug,
Thanks for the input! That check box was checked, sorry for not including tat fact in the list.
I have resolved the issue! Turns out that we were so focused on making sure their Barracuda Firewall was properly configured that we failed to realize that the Windows Firewall was turned on on the MAS Server (is is a new test server). We turned off the Windows firewall, restarted the services and recycled IIS. That did the trick!