Shameless bump.
Is any other Mac user in the world having trouble connecting to the MSN network?
I'm having this same problem and some others (like contacts going offline, messages not being delivered, etc), using aMSN, Adium, and/or MSN Messenger for Mac, and I've tested with another account, and the same happens.