Well I spent a few hours with Microsoft support today throubleshooting an issue with Exchange Web Services, Unified Messaging, and Autodiscover. It appears that the web.config file contains a variable called %ExchangeInstallDir% which is invalid. The web application can't interpret what this variable is because it isn't set on the OS anywhere.
The issue is visiable in two ways:
1. Try to navigate to https://serverfqdn/ews/exchange.asmx (it will fail)
2. Try to run the "Test-OutlookWebServices -Identity email@example.com fl" and it will show you all kinds of errors.
The fix was to open the web.config files at:
C:\Program Files\Microsoft\Exchange Server\ClientAccess\exchweb\ews
C:\Program Files\Microsoft\Exchange Server\UnifiedMessaging\WebService
...and replace the %ExchangeInstallDir% with C:\Program Files\Microsoft\Exchange Server\
Restart IIS using "IISRESET" and you should be okay.