Okay, the only thing I did different in the past few months was adding my work email account (Exchange account). I noticed in the Groups settings that there was a separate row with my work email checked.
When I unchecked it, new contacts disappeared. When I check it, they returned.
After I deleted my work email account on my iPhone, then added the new contacts, everything is back in sync.
Ah ha, that's it.
On the phone in Settings>Mail etc> under Contacts you had the Default Account chosen as the Exchange Account instead of iCloud.
BTW now that you removed Exchange, you won't have a Default Account setting under Settings>Mail etc> Contacts unless you have another account entered. When you add the Exchange Account back you'll then see the Default Account option.
After creating the new account go back to Settings, then tap again on Mail etc for the Default Account option to appear. Here's an article
that will help.If you are creating a new contact manually by tapping the plus button within either the Contacts or Phone apps the contact will only be created in the default account if more than one account is selected from the “Groups” listing.
If you want to create a contact in your non-default account, you must first go to the “Groups” by tapping the button in the top-left corner in the Contacts app and then ensure that the group that you want to create the new contact in is the only group selected. You can then return to the Contacts view, tap the plus button and create the contact as you normally would.