This is similar to what gutschik said but with a tad more info...I was having this problem at work yesterday and thought it had something to do with port 993 as well. I talked to the IT guy and he said that port 993 is unblocked. I also have a gmail and yahoo account that both use the same port and I had no issues with those accounts. It appear now that the new iCloud setup sets the default incoming mail server as p03-imap.mai.me.com whereas the Lion version was simply imap.mail.me.com for whatever reason our fortiguard router does not like the p03- part at all. At home I have no issues on a airport setup nor did I have any problems on 4g on my iphone. Both Mail and Notes use the incoing mail server to connect and sync it appears.
The biggest pain in the butt is that you can't simply just go into the prefs and change that setting for some reason(it's greyed out). You have to actually create a fake account that the apple setup can not verify thus taking you to a setting page where you can enter the information manually and remove the p03- part. Once I did that boom, mail started working and so did notes sync, but now I essentially have two different iCloud accounts listed...one for mail and notes and the other being the default apple set up one with everything else. Hope this helps until there is a more permenant solution. If anyone figures out why some routers reject the p03- part please let me know so I can pass this along to the IT guy.