When your contacts show up as emails this means that they have no name set (so a person with an email of jsmith@example.com would be called John Smith) as your Messenger client has not had them sign in before and thus no information has been sent yet. Messenger then defaults to the person's email address:
If no Messenger nickname > use first and last names; if none > use email.
I hope I explained it alright
I'm not 100% sure if that's how it works, but it seems to be so.
EDIT: @Joshua: That is a plausible workaround, yes, but highly impractical if you have a large amount of contacts.