Since custom name feature was introduced, I've never heard a problem like that.
Try to reinstall MSN Messenger and don't patch it, or maybe use different patch.
See if your contact can rename himself.
I once encountered a problem, but it was related to Stuffplug and it was in convo windows.
My problem was the chat only name overrides the costum name feature.
I don't know if it has been fixed or not.
/ –
