If you go to your Connections screen and test your IMAP connection, is it successful? That's the first thing I'd check.
We have that issue as well occasionally with connections that are correctly configured. Most of the time, they were nicely, but occasionally they decide to complain, and a few minutes later they decide to work again. Sometimes, Office365 has connection issues on Microsoft's end which we can't do anything about, so we just have to wait it out.
It's a bit annoying, but we figure that since the connections usually come back within a few minutes anyway, there are other battles that are more worth fighting. I realize this wasn't much help, but hopefully it's a small consolation to know you're not alone in this issue.