Contacts Sync problems: phone contacts not syncing to Google
Make sure that when you add a contact, the contact type is set to GMail.  If it's set to phone then it will not sync to GMail and will stay solely on the device.

Contact Type is the first field on add new contact and is set to phone by default.