Since updating to Mavericks the Messages app doesn't display the contact names for people I've been communicating with iMessage, it shows their phone number instead. My messages thankfully still stay synced between my iPhone and Messages on Mavericks.
When Messages receives an iMessage, it matches the source with an entry in your Contacts. If you don't have a matching contact, you just see the phone number or email address of their iCloud account.
If your phone syncs its contacts to iCloud, Facebook or some other source, and you would like your contacts on your computer to also sync to this source, open System Preferences then choose Internet Accounts. If you use iCloud for syncing, choose iCloud from the list of accounts then tick the "Contacts" checkbox. If you use Facebook, add a new Facebook account and your friends list's contact information will download and stay up-to-date as they change it. Pretty much any other source of contacts you can think of can be added here, either through one of the main account types for the major providers or "Add Other Account" for standards-based things like LDAP & CardDAV.
Wait a few seconds after adding the new account and ensuring "Contacts" is checked off, and your iMessages should now match up names where there were phone numbers or email addresses before.
While you're in Internet Accounts, you can also add certain other message sources to Messages, if you desire. As an example, you can add a Google account and tick the "Messages" checkbox, and then your Google Talk messages will appear inside of Messages alongside your iMessages. AIM, Yahoo! and Jabber round out the other options; no Facebook yet.
There are a number of other routes to access your Messages and Contacts sources (namely via the iCloud preference pane or via the "Accounts" tabs present in each app's preferences) but Internet Accounts is the one-stop source for all of this. Each different route controls the same information, back here in the master source.
I had this same issue and it turned out that I had to include the country code for each contact's phone number to get their name to show up in Messages. This may be an artefact of the Australian telecom I use, but to make it work I need to add +61 to each contact.
I noticed this because the country code was included in the phone number that Messages was using instead of the name and thought it odd. Sure thing, when I change the corresponding number in contacts to match exactly what Messages was showing, the persons name and thumbnail image became viewable instantly.
In your case, it may be some other difference between the number your carrier shows and the number you have in your contact's details.
The answer to my non-syncing contacts in iMessage was to ensure that the international dialling code is added to all of my contacts as this is what our local network (Vodacom) uses. The system then successfully matches the number the network uses with the number in my contacts and then displays the name and picture successfully.
Thank you for your help with this.
Same thing was happening to me. I opened "Contacts" on my Mac. It said it could not access my Exchange contacts and I needed to input the password for my Exchange account. Once I did that all my contact names showed up in iMessage.
Apparently iMessage pulls contacts from the Mac "Contacts" and that needs access to the Exchange contacts.