If you're trying to connect to an exchange server, contact the Exchange administrator - there are too many ways of setting that up for us to guess what you should do, but he's know.
If you're connecting to a Microsoft emailbox, let the app choose the method, and try again. It could take a few tries. (It could also take a few days - email servers have been known to go offline for a while.)