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.