Mac Mail not syncing with Address Book

My address book and Mac mail are not working nicely together.

I have a contact in my address book, and for this example we will call him John Doe. Here is John Does info.

First Name: John
Last Name: Doe
E-mail address: jdoe@gmail.com

When I receive e-mails from 'jdoe@gmail.com' in my Mac Mail application the 'From' field displays some random nickname for 'John Doe' even though his e-mail address matches the one in the address book.

How do I get 'John Does' name to appear in my Mac Mail instead of some random nickname.

In my understanding, I thought Mac Mail synced up e-mail addresses with the contact book and displayed the appropriate corresponding name.

Does that make sense?