When I try to sign into MSN Messenger, I get an error saying: "your display name could not be changed. Please try again later".

I can sign in on a different machine, onto Web MSN on mine. Any ideas? Have uninstalled and reinstalled messenger, even the new 8 beta.

I did have Trillian installed, but uninstalled it ... maybe that screwed it up?