I've had these on new installs as well, usually it's a dns issue. For a temporary work around you can add all of your domains to: server management -> network services -> email -> advanced tab -> Relay Email From Hosts/Domains/IP Addresses