WLM: Display Name- Contacts see an old one(s) i've long since chan

Hello,

i'm using Windows Live Messenger 8.5.1302.1018 on Vista Home Premium
(recently changed from XP)
Like most people, i change my Display Name now and then.
However, my friends are telling me that they don't see my "current" display
name,
but an old one(s) that i've already long since discarded and changed.
For example: If i go through like this: 'A', 'B', 'C'... and now i'm on 'M',
they say that what they see on their screens is 'H', not 'M'!
This is very frustrating, as you can imagine! Can't find an answer anywhere.
(friends using WLM, on XP's and Macs.)