It does have to do with the IMAP upgrade - the problem is that STARTTLS is now being advertised in the IMAP banner. One solution might be to force Eudora to make a non-ssl connection if that's an option.
I don't know how certificate management works with Eudora, I do know that it's sometimes a little tricky to trick Eudora into accepting the self-signed certs. I'm pretty sure it's possible though.
Hopefully someone else here can help - if not, I'll get one of the support people to look into this further (it's information we should add to the kbase at some point too).