A little more information, we did a trace and found that it's picking up access to another domain. That's why it's failing. Messy. Now contacting the other Exchange admin and let the excitement begin!
Would love to help but the current description is too vague. These settings are distributed through autodiscover, you can use the Test Automatic Email Configuration feature in Outlook to find out what the clients tries to do to obtain the settings, and what settings it gets from te server.
The Test Automatic Email Configuration test...(ha,ha) show the configuration is going to wrong way. Autodiscover is send the routes to servers that are not in our domain or control. These users were migration over to our domain but their workstations,accounts, etc... log into the other domain for work stuff. Only their email system is on our domain. Autodiscover on the other domain needs to be changed or we need to move faster and get those systems on our domain.
We are doing things backwards here but that's typical!