I have found out what the issue is. The IOS 12 native mail client has drastically changed its authentication, fallback and error handling methods. With our example historically the password field in the exchange profile had some characters in it, IOS 11 just ignored these characters and accepted the certificate before looking at other credentials. Now in IOS 12 the password is being used before the certificate was checked resulting in a failed authentication but instead of returning the usual ' enter your password' dialog like in IOS 11 it now returns a vague ' cannot connect to server' message.
We have the same issue and have logged a ticket to AirWatch. Please let us know if you hear any more. I tested also without AirWatch on a personal device and changed my Office365 Exchange account password. On my 12.01 device there was no prompt for the new password. Our corporate devices have account restrictions enabled in an iOS profile which means the user cannot go into passwords and accounts on the device to change their password.
We are experiencing this issue with O365 on iOS 12.1 and 12.1.1.