I've had similar issues on my V20 and they all seem to be related to Google itself and how it pulls the info. When you ask it to dial a contact, it's not going through your phone list. It goes to your cloud storage contacts on their servers. So make sure your account settings are still synced (you'll get an error message in the sync settings screen if not working), and that you didn't deactivate needed permissions in a related app (which was part of my problem).
This thread gives more details on what my issue was, just to show you how odd the solutions can be sometimes. For me, it was a Google Play Services permission preventing me from voice dialing newly added contacts.