I had the same problem with my Galaxy S5
My solution was to use the pull-down menu at the top of the phone's add contact screen, and select "Google", then go ahead and add the contact. This is not mentioned in the User Manual, or anywhere else I can find...I found it by trial & error.
The...