The new patch or update created more problems than it fixed.
mabe it is some help.This will clarfy either one of two things...'
1) The new msn looks for you computer filepath to link contacts
2)or the contacts stored on your msn, are stored in msn server.
im under the impression when you log in your contacts are stored on a msn server thuss allowing you to bring your msn up on a friends computer...
Sometimes on msn especially with live messaging contacts can be lost due to different versions i.e someone is on yahoo msn .. insted of say windows live msn.
im pretty sure your contact should still be there.
Try using a program called
amsn
www.amsn-project.net/Untill the new msn patch becomes stable enough install.
This programme is good if your contacts have different version and for the mean time.