I changed my Windows Live ID from a non-hotmail email ID to another non-hotmail ID. I understand that contacts can appear offline for up to 48 hours in order for the servers to propagate my new email address.

However, it has been nearly 4 days already and still my entire contact list is appearing offline.

Is there any way I can rectify the situation?

If anyone could offer me any help on this, I would greatly appreciate it! Thanks in advance.

Are you sure they all added you? If they blocked you when you added them, then you'd need to lst them know somehow

I have the same problem. I changed my old Live ID with a new one, 3 days ago... But all my contacts are appearing offline, and I am appearing offline to them. Although my address appears to have been changed in Live.com, my contacts still see me as my old ID, and offline... In Live.com, says that it can take up to 48 hours for the change to take effect, but I have already been waiting 60 hours...
The "Contact List Cleanup", shows that all of my contacts have me in their contact list...

Well, I waited for 4 days... Then I exported all of my contacts, I completely closed the Live Account, and I signed up from the start... And I imported the contacts...

Pros and Cons

Pro: Messenger had already installed my settings in this PC, the backgrounds and the preferences for this account. And when I closed and reopened the account, Messenger did not "understand" that it was another account, so I didn't have to set my preferences all along...

Pro: When I closed the account, I didn't wait at all to sign up for a new one. I used the same e-mail address and Live accepted it...

Con: All my contacts must select "Accept" when they see my invitation... So, I have to expect that a couple of them will select "Refuse" thinking that I might be some kind of spammer...