I've heard a lot of people have been getting this recently...it may be something to do with the Messenger network.
My advice would be to uninstall and reinstall messenger, or (if the feature is available) try a 'Repair.' To do this, (I assume you are using Windows XP) go to:
Start> Control Panel> Add/Remove Programs, then find MSN messenger in the list and see if the 'Repair' feature is there. If not, reinstall it.
Hope this helps :)