I have been banging my head over issues with the new Exchange 2013. Install seems to go well but doesn’t seems to want to coexist with Exchange 2010. Moments aware from calling in a product support case I find Cumulative update 1 for Exchange Server 2013 (KB2816900): http://www.microsoft.com/en-us/download/details.aspx?id=38176

It seems I now need to wait about an hour for this update to complete before I know if this fixes the issue*

* issue I am having is email routing between Exchange 2010 and Exchange 2013

More on this here