@Brooks & @GeorgefromGermany
If people actually read the Release Notes:
http://technet.microsoft.com/en-us/library/jj150489(v=exchg.150).aspx
Mail flow stops after Exchange 2013 SP1 is installed After you upgrade to Exchange 2013 SP1 from a previous version of Exchange 2013, mail flow might stop working on servers that have the Client Access server role installed. This happens because, even though the Microsoft Exchange Frontend Transport service starts after Setup completes, it doesn't correctly detect that it can start sending mail again. This issue doesn't occur on new installations of Exchange 2013 SP1.
To work around the issue, restart the server after Setup completes.