Make sure that when You are syncing the phone with iTunes that you go to the contacts tab and that you are syncing with your address book ... If nothing is checked when you sync, your contacts on your phone will be gone Happened to me.
