What is your preference setting for contacts: on your phone or icloud?
And what group of contacts is the contacts app currently showing? both icloud and those that are on the phone or only phone/icloud?
Could be that you save contacts to your phone but only showing icloud contacts, or vise versa.
it would help if you describe what steps you take to add a contact.