This is actually caused by a bad UI (IMHO) which kinda gets you to configure it wrong. What has happened is that the outgoing has a tick box saying to use SSL and asks for a server name, while the incoming asks for a URL. It automatically puts in http:// so naturally you fill in your server, i.e. http://myexchange
However Exchange runs on SSL so it actually needs to be https://myexchange
If that doesn't help then open up the URL you are putting in, in a web browser and see if it works. You'll get a lot more information on the real cause.