There have been a number of posts following this latest update and issues with Mail but mostly connected with Gmail accounts on the Authentication side, but strangely enough I also had a problem with the SMTP side of the two mail accounts I use.
After the update I noticed in Mail's Connection Doctor that for both iCloud and my third party ISP account the SMTP Server was not showing a successful connection and login to the server, for it to happen on one ok, but both seemed strange. The SMTP server is responsible for sending by the way.
The error report within the Mail App itself (when you see the triangle next to the account) reported something like a connection could not be made because one already existed (can't remember exact wording). This was strange because I hadn't used any of my iDevices so as far as I could tell it was just the iMac trying to establish a link.
That made me suspect that somehow the two accounts on the SMTP side were getting mixed up and causing the conflict which I then tried to prove by turning off iCloud, when this was done my third party ISP account was functioning again, but reenabling iCloud caused the issue to return.
I ended up turning off iCloud Mail altogether under the Account Information tab of Mail Preferences and then using the "-" button to delete the ISP account after exporting all messages (I still use a POP account so content is downloaded on to the iMac and not kept on server). After closing Mail and rebooting I added back my ISP account (had some configuring of port number and SSL by hand though) and then reenabled iCloud.
That seemed to fix the issue.
Had one strange thing though, when reenabling iCloud (ticking the box under Account Information) I noticed under the Server Settings tab it said "None", I then had to select iCloud under that dropbox, but it didn't appear to "stick" so I had to do this several time switching between the account information views before it finally stayed selected.
I hope some of the above gives you some further ideas (and sorry for using "strange" so many times), I appreciate that having just two accounts made this a little easier for me but may be you could just concentrate on getting the most important one working first (remove all others after backing up messages) and if successful add the others back one at a time.