Do you still have your old phone, can you turn it on? I'm guessing the missing contacts were accidentally entered as a Phone Contact and not a Google Contact.
I thought, and apparently WRONG, that when my phone synced.my contacts synced with Google. What's the point in syncing and West is being synced, if not my contacts???' OMG another hard learned lesson????
When you first open the Contacts app it should ask for the default type...Phone only, Google, etc. If you select Google then they will always sync to your new phone. If they were entered as a Phone Contact then they stay on that phone only and no syncing. Not sure what happened in your case though. It could just be a glitch, or something strange.