The name cannot be resolved. New account on Exchange 2013

So here is the deal.

We created a new account for a new employee on our nice shiny new Exchange Server 2013.
When we try to setup the user account on outlook we are prompted with the following:

"The connection to Microsoft Exchange is unavailable. Outlook must be online or connected to complete this action."

So then I try to manually configure the account by first adding the FQDN on the exchange server then the IP Address and I receive:

"The name cannot be resolved. The connection to Microsoft Exchange is unavailable. Outlook must be online or connected to complete this action."

AWESOME!
So here are a few things I try to determine if it's the user profile, the computer, or the account itself.

- I log on as myself on the same computer and attempt to add my account on outlook... SUCCESS! so now I know it's not the computer.
I log them on to another computer and attempt to do the same... FAIL... I still get the error. So we know it's not the profile or the outlook version as one attempt was on outlook 2010 and the other on outlook 2013.

- So i go back to the original computer and see if I can manually configure the account and exchange proxy settings... SUCCESS!!! it worked! and now the end user can log onto their outlook with no issues.

My problem is that I shouldn't have to do this and would sure like to know why all the accounts I'm creating now will not just auto configure.

Also, I compared the account memberships and permissions to another similar working account in AD to ensure all things were the same... Could this be service related on the server side? Perhaps a DNS issue?
I've checked the services on the server and all of them minus anything pop3 is running.

I KNOW FOR SURE THE PROBLEM IS NOT ON THE LOCAL COMPUTER BUT IN OUR SERVER ENVIRONMENT

I'm not sure how relevant this is to my issue but, we do have 2 different types of emails... for example;
our main doman email usually looks like

user@ABCinc.com
but we also have
user@DEFinc.com & user@GHIinc.com

this specific user has email:
user@DEFinc.com only...

not sure if that makes sense but I figured I'd throw it out there just in case... Also the account was created through the ECP on exchange and not on ADUC (i didn't do it, i swear!)
MukooSystem AdministratorAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Will SzymkowskiSenior Solution ArchitectCommented:
If accounts are not automatically finding there mailbox databases then Autodiscover is not working properly. I would suggest you check your autodiscover URL to ensure it is set properly. It wouldn't hurt to also check DNS as well.

Understand and Configure AutoDiscover
https://technet.microsoft.com/en-us/library/bb124251%28v=exchg.150%29.aspx

Will.
MukooSystem AdministratorAuthor Commented:
But why would the autodiscover work on existing users?
DrAtomicCommented:
Existing users have their autodiscover response stored in AD, where as new ones don't. See https://technet.microsoft.com/en-us/library/jj591328(v=exchg.141).aspx#BKMK_OutlookAndAutodiscover

Here's a good tool to test autodiscover functionality: https://testconnectivity.microsoft.com/

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Will SzymkowskiSenior Solution ArchitectCommented:
To test autodiscover internally just use the Outlook client.

- right click the Outlook icon in the system tray
- select Test-Email Connectivity
- Run the Autodiscover test and see what those users are pointing to for Autodiscover URL.

Will.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Exchange

From novice to tech pro — start learning today.