Office365 will accept connections and successfully authenticate even when the user doesn't have permissions to access the server by IMAP, and this is the exact error it gives in that situation.
To resolve it, go into the Office365 panel, open the user, and ensure that the IMAP permission is checked.
