I have had this issues a couple times....I go to create a new contact (on the Droid, not through gmail), put in all the information, hit done, and it tells me "contact saved." I go to my contacts, and it isn't there! FRUSTRATING.
I then go to my gmail account and creat the contact through there and let it sync to my phone.
Anyone else had this problem?