I just spotted that Exchange 2013 Cumulative Update 3 was released by the Exchange team at Microsoft. It's a huge 1.5 GB in size. It's great to see updates coming out so quickly, it means that problems are being addressed in nice, quick order.
Before launching the installer though and updating your Exchange 2013 environment take a moment to consider the Enterprise Vault Compatibility Charts. They only go as far as Exchange 2013 Cumulative Update 2. So.. in sort, until the charts are updated, don't update Exchange. You might break something in Enterprise Vault, and Symantec will not 'guarantee' that it can be fixed, until they have certified the Cumulative Update.