You're probably adding them to a Group that isn't visible. Open the Contacts.app and in the top left corner press the Groups button.
Make sure all your Groups are checked so that they are visible.
I've had this happen to me before. I sync my contacts with Google and the iPhone has the bad habit of defaulting to the "On my iPhone" group and if that isn't checked to be visible I don't see those contacts, even when I add them. I had about 15 or so added before I caught this and fixed it.