“My MSN contact list has about 140 people on it whose emails would be highly difficult to remember”
So,
“email your friends with your new address”
may not be 100% possible for his option. Unless he uses e-mail client program (i.e. Outlook, Incredimail), he could retrieve such e-mail addresses.

Just to add a handy tip, in the future, you have to keep your e-mail contact list in a separate file, like a TXT FILE or something (so, in case of emergency, you will still have it, it saved me time, it could save yours too). For PASSWORDS, you have to be sure to change it in a regular basis. And for SECURITY REASONS, in public computers and/or Internet café, I am always checking for malicious programs running like key loggers and such, trying my best I guess, well that’s just me.

BTW, in line with the subject, my friend’s YAHOO! Account had the similar problem; his PASSWORD had been changed, but cannot reset it because of S-2-P-D-T (he forgot his magic A to the MAGIC Q).

Yo!