Hey dudes. I had this problem as well. I kinda fixed it by signing onto web messenger and changing my name. I logged back onto the real msn and hey presto for some reason I can change my display name and crap.
WTF is going on?
Oh and you need to re-add your contacts.