I have an HTC Desire Z, Android phone, running Froyo 2.2, with my contacts synced with google contacts.  When I entered a new contact on my phone, it would disappear when it synced with google contacts.  I could not find a solution online, but discovered this by accident.

My google contacts were full (because of another syncing problem with mac, multiple computers and self-duplicating contacts), and any new contacts were simply being rejected.  Either the phone is not handling this error correctly, or google is not telling the phone that it is happening.

I deleted some google contacts and the problem was fixed.

Horray!