I had a network error problem with MSN account while any other protocols, including Skype and ICQ worked just fine.

What helped me was to install MSN (pecam) protocol from available repository. After deleting the previous MSN IM account, I have re-installed it back again, this time with MSN (pecam).
Worked like a charm.