In iPhone Settings -> Mail, Contacts, Calendars -> Contacts, there is a message:
New contacts created outside of a specific account will be added to this account.
What does that specific account referring to?
This happens if you also have your iPhone setup to sync to outlook via a microsoft exchange server.
The key here is to setup your "default account" to also work the same way when you are manually adding contacts to your iPhone.
Under Settings -> Mail, Contacts, Calendars -> Contacts -> Default Account you can select an account to have your contacts created in when you create a new contact.
"outside of a specific account" refers to your exchange account setup.
If you have any issues where contacts created on your iPhone don't sync correctly with your exchange account then you should change the default account to point to your exchange account.
more info and discussion about this (as well as potential sync issues with exchange server) can be found here.
Hope this helps.