Extremely odd since your contacts should be stored on a server elsewhere. Maybe you should check if the same thing happens on another computer (maybe get your hands dirty on a PC), or you could try using Proteus x (http://www.proteusx.com). Proteus is much better BTW, it only nags you once in a while demanding that you pay a small fee.
Then I'd just ditch the new MSN messenger client. There are sleeker alternatives out there. Like I mentioned earlier Proteus is a good option and it offers more than just MSN connectivity. I switched to that client because It'll combine other IM services in one client and it has a wider variety of gimmicks to make the experience more enjoyable. Especially the addressbook synchronisation.
That's as far as I can help there.
I'm a new switcher - and MSN Messenger 4.0 annoys me that it keeps logging me out...
I can't see others pics (attached to their profiles) or display one anymore..
I can't do video chatting with my iSight - yet PC Messenger allows it...
sigh
I have been using amsn for sometime as an alternative to MSN Messenger. I have had no problems with it, file transfers have been working fine, and it supports display pictures at normal size.