Ask your friends to stop using icons in their nicks?

Seriously, though, I'm pretty sure you can rename contacts locally to make the names more readable.

EDIT: Yes, I just did it for one of my MSN contacts. I was able to replace his long, icon-riddled nickname with his real name by editing his contact record.