I answer yes to the dialog to correct the logon information.  I verify the Service Account: SMTP is set to serviceaccount@mydomain.com, enter the Service Account Password, and verify the Exchange Server is the net bios name of the server.  It still fails.

The Add2Exchange and SQL service are both running and using the service account and password that I used above.

I verified that the service account is showing up in my Outlook address book (on my desktop).  

This is a fresh install on Server 2012 R2 and Exchange 2013.

The password is correct as I can start both A2E and SQL services with the service account and password. .  You can see from the error below the format is correct  and I have the correct server name.

I have an A record for the external mail hostname that point to the mail server.

Log Name:      Add2Exchange

Source:        Add2Exchange
Date:          5/7/2014 6:25:38 AM
Event ID:      5001
Task Category: None
Level:         Error
Keywords:      Classic
User:          N/A
Computer:      SRV02.dsc.com
Description:
RDO Logon Session Failed To Get Default Folder for Mailbox 'ZADD2EXCHANGE@MYDOMAIN.COM' for Server 'EXCHSRV' Error: -2147221231 Error in IMAPISession::OpenMsgStore: MAPI_E_LOGON_FAILED
Make sure your code runs under the Windows user identity that has MAPI profiles.
When running in a service (including ASP under IIS), set your code to run under
the Windows user account that has MAPI profiles.
When connecting to an Exchange Server, you can also use RDOSession.LogonExchangeMailbox
which does not require an existing profile.
ulVersion: 0
Error: The information store could not be opened.
Component: MAPI 1.0
ulLowLevelError: 0
ulContext: 646 At Line 210

Add2Exchange Console v16.5.1953