If you have already verified your email address. Log into Live Messenger and click the drop down menu by your email address. Click on "Change Display Name"
remove (EMAIL ADDRESS NOT VERIFIED) from behind your email or change your entire email address to a different display name.
