Example A.
Why aren't both Joshes on iCloud/iMessage?!??!?!?
I'm not saying you're not having issues, but are you suing iMEssage to highlight that Josh Bush is not in your contacts on your mac?
Just curious as to why you're showing iMessage.
Anyway, I had some issues syncing right at the beginning when I first got my iPhone 5, but I guess it was still syncing, as eventually it worked.
Are contacts missing from both devices, or are all contacts just missing from one? That would be first question. It if it's all one, then you know where the issue may lie - could be that devices is not syncing, or maybe a view not showing certain contacts?