well if you add contacts while on the go, when you plug your iPhone into iTunes a message should pop up from iSync or AdressBook asking you to sync your contacts. Check AdressBook to see if all of your contacts match cause thats where your iPhone stores and retrieves that information.
I assume you are on a Mac due to your specs you have listed.