Ok, I have pretty much ruled out the IMAP problem. I installed Thunderbird and tried it out with the accounts, they are both fine. Now my big problem is with Imp, where it gives the "error viewing the requested message"
It only gives this error on the most recent message (so, if I send a message to the account I can't read it but I can now read the one that was the recent one before mine)