This week I’ve had two clients have sudden issues with auth prompts in previously trouble-free Exchange 2013 environments. One of them worked with a Microsoft engineer and eventually determined that a recent patch pushed out on Tuesday that was meant to block the Poodle exploit caused issues with NTLM with HTTPS authentication. Since Exchange 2013 uses RPC/HTTPS connections even on internal networks, this means that internal MAPI clients can be disrupted by this patch.
More information here:
These articles describe problems with Outlook, SharePoint and shared drives caused by this patch.
If you recently had auth prompt issues crop up in your E2013 environment, check for this patch, try uninstalling it from your Domain Controllers and your Exchange server. It might resolve the issue.