Users are getting prompted for Autodiscover after DNS change

It may not be something that you have done.
Do you have autodiscover.example.com resolving to your Exchange server?
If so, check whether

https://example.com/Autodiscover/Autodiscover.xml 

resolves.

If it does, then that is the problem and you need to get your web host to stop it from doing so.

Simon.

What is happening is a problem with how Exchange AutoDiscover works.

If you go to https://testconnectivity.microsoft.com/
Run the tests, you'll notice that the very first test autodiscover does is look for

https://yourdomain.com/AutoDiscover/AutoDiscover.xml

Then:
https://autodiscover.yourdomain.com/AutoDiscover/AutoDiscover.xml

-- As you can see, if your DNS @ record points to the same IP address as your DNS A record for www.yourdomain.com, then that autodiscover request will go to your WWW site, where it finds a certificate for a secure website that has no relation to your production site, and so it throws the stupid error.

I cannot believe how stupid autodiscover is for that reason (among others).

If you simply browse to https://yourdomain.com - you'll get to the same site, same cert that is showing up in your autodiscover SSL error popups.

How to fix it?  Well, what I've done is point the @ record to my exchange server, or if that creates website problems, I create a new web server instance listening on port 80 only, with the domain of 'yourdomain.com' then create the full path it is looking for:

https://yourdomain.com/AutoDiscover/AutoDiscover.xml

Create a folder called AutoDiscover, and in that put a text file you've renamed to AutoDiscover.xml

Within IIS, you set up an HTTP redirect so that anyone that looks for that particular file will get a HTTP redirect to: https://mail.yourdomain.com/AutoDiscover/AutoDiscover.xml

Then, at the root of the site, I put a hard redirect to www.yourdomain.com, so anyone looking for http://yourdomain.com/foo  will be redirected to http://www.yourdomain.com/foo

Hope that all makes sense...
Joel

What is the @ prefix of an A record used for?

Does that effect the active sync devices I have?

The @ prefix is for situations where people do not put www or any other prefix in front of your URL.

http://example.com  - is an @ prefix A record
http://www.example.com - is a standard A record

Another question is why about half of my users are getting the popup but the rest don't?

I also ran the test on microsoft and got all failures.

Can you post the results of TestExchangeConnectivity.com?

Also, what were the results of you browsing to https://yourdomain.com - did you get the cert error?

Attempting the Autodiscover and Exchange ActiveSync test (if requested).
       Testing of Autodiscover for Exchange ActiveSync failed.
       
      Additional Details
       
Elapsed Time: 3158 ms.
       
      Test Steps
       
      Attempting each method of contacting the Autodiscover service.
       The Autodiscover service couldn't be contacted successfully by any method.
       
      Additional Details
       
Elapsed Time: 3158 ms.
       
      Test Steps
       
      Attempting to test potential Autodiscover URL https://kkbcpa.com/AutoDiscover/AutoDiscover.xml
       Testing of this potential Autodiscover URL failed.
       
      Additional Details
       
Elapsed Time: 1548 ms.
       
      Test Steps
       
      Attempting to resolve the host name kkbcpa.com in DNS.
       The host name resolved successfully.
       
      Additional Details
       
IP addresses returned: 167.68.20.163
Elapsed Time: 37 ms.
      Testing TCP port 443 on host kkbcpa.com to ensure it's listening and open.
       The specified port is either blocked, not listening, or not producing the expected response.
        Tell me more about this issue and how to resolve it
       
      Additional Details
       
A network error occurred while communicating with the remote host.
Elapsed Time: 1510 ms.
      Attempting to test potential Autodiscover URL https://autodiscover.kkbcpa.com/AutoDiscover/AutoDiscover.xml
       Testing of this potential Autodiscover URL failed.
       
      Additional Details
       
Elapsed Time: 1387 ms.
       
      Test Steps
       
      Attempting to resolve the host name autodiscover.kkbcpa.com in DNS.
       The host name resolved successfully.
       
      Additional Details
       
IP addresses returned: 167.68.20.163
Elapsed Time: 73 ms.
      Testing TCP port 443 on host autodiscover.kkbcpa.com to ensure it's listening and open.
       The specified port is either blocked, not listening, or not producing the expected response.
        Tell me more about this issue and how to resolve it
       
      Additional Details
       
A network error occurred while communicating with the remote host.
Elapsed Time: 1314 ms.
      Attempting to contact the Autodiscover service using the HTTP redirect method.
       The attempt to contact Autodiscover using the HTTP Redirect method failed.
       
      Additional Details
       
Elapsed Time: 199 ms.
       
      Test Steps
       
      Attempting to resolve the host name autodiscover.kkbcpa.com in DNS.
       The host name resolved successfully.
       
      Additional Details
       
IP addresses returned: 167.68.20.163
Elapsed Time: 9 ms.
      Testing TCP port 80 on host autodiscover.kkbcpa.com to ensure it's listening and open.
       The port was opened successfully.
       
      Additional Details
       
Elapsed Time: 71 ms.
      The Microsoft Connectivity Analyzer is checking the host autodiscover.kkbcpa.com for an HTTP redirect to the Autodiscover service.
       The Microsoft Connectivity Analyzer failed to get an HTTP redirect response for Autodiscover.
       
      Additional Details
       
The URL specified in the location HTTP header was not HTTPS. URL: http://www.autodiscover.kkbcpa.com/Autodiscover/Autodiscover.xml
Elapsed Time: 118 ms.
      Attempting to contact the Autodiscover service using the DNS SRV redirect method.
       The Microsoft Connectivity Analyzer failed to contact the Autodiscover service using the DNS SRV redirect method.
       
      Additional Details
       
Elapsed Time: 21 ms.
       
      Test Steps
       
      Attempting to locate SRV record _autodiscover._tcp.kkbcpa.com in DNS.
       The Autodiscover SRV record wasn't found in DNS.
        Tell me more about this issue and how to resolve it
       
      Additional Details
       
Elapsed Time: 21 ms.

For the https, I get a page not found error.

Okay, I need the error message that clients are getting.
- Does the error message they get talk about the secure.emochila.com certificate?

Here is the popup.

There is no https or emochila reference
New-Bitmap-Image.bmp

ok.  I just wanted to make sure there was no issues with what I have done and allowing it was ok.

I guess that is the question I should have asked at the beginning.

I should have requested the picture you referred to in the beginning rather than just assume.