[HTC One X] -=nezero=-:
Looks to me like its a Google Issue - I just have no idea where to report it to get it fixed (Google support is terrible unless you are using a paid for service!)

I tried getting a logcat of it happening to see if there is anything i can spot going wrong.

D/PowerManagerService( 508): acquireWakeLock(41c3a408): PARTIAL_WAKE_LOCK , tag=SyncLoopWakeLock, flags=0x1, pid=508, uid=1000
D/PowerManagerService( 508): acquireWakeLock(41ed3f78): PARTIAL_WAKE_LOCK , tag=*sync*_com.android.contacts_Account {name=*************, type=com.google}, flags=0x1, pid=508, uid=1000
D/PowerManagerService( 508): releaseWakeLock(4181b5d0): PARTIAL_WAKE_LOCK , tag=SyncManagerHandleSyncAlarm, flags=0x1
D/PowerManagerService( 508): releaseWakeLock(41c3a408): PARTIAL_WAKE_LOCK , tag=SyncLoopWakeLock, flags=0x1
D/PowerManagerService( 508): acquireWakeLock(4252f8f0): PARTIAL_WAKE_LOCK , tag=SyncLoopWakeLock, flags=0x1, pid=508, uid=1000
D/PowerManagerService( 508): releaseWakeLock(41ed3f78): PARTIAL_WAKE_LOCK , tag=*sync*_com.android.contacts_Account {name=*************, type=com.google}, flags=0x1
D/PowerManagerService( 508): releaseWakeLock(4252f8f0): PARTIAL_WAKE_LOCK , tag=SyncLoopWakeLock, flags=0x1
D/PowerManagerService( 508): acquireWakeLock(41ec0eb8): PARTIAL_WAKE_LOCK , tag=SyncLoopWakeLock, flags=0x1, pid=508, uid=1000
D/PowerManagerService( 508): releaseWakeLock(41ec0eb8): PARTIAL_WAKE_LOCK , tag=SyncLoopWakeLock, flags=0x1

....

D/ContactsSyncAdapter( 9855): ForbiddenException, ignoring rest of feed
D/ContactsSyncAdapter( 9855): com.google.wireless.gdata2.client.ForbiddenException: Could not fetch feed https://www.google.com/m8/feeds/groups/email@google.co.uk/base2_property-android?showdeleted=true&orderby=lastmodified&updated-min=2013-08-28T07%3A57%3A30.603Z&sortorder=ascending&max-results=500&requirealldeleted=true com.google.wireless.gdata2.client.HttpException: Received 403 status code: <html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8">
D/ContactsSyncAdapter( 9855): <title>Error
D/ContactsSyncAdapter( 9855): 403
D/ContactsSyncAdapter( 9855): (Forbidden)!!1</title>
D/ContactsSyncAdapter( 9855): <style type="text/css">
D/ContactsSyncAdapter( 9855): *{margin:0;padding:0}html,code{font:15px/22px arial,sans-serif}html{background:#fff;color:#222;padding:15px}body{background:url(data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKsAAADVCAMAAAAfHvCaAAAAGFBMVEVYn%2BH%2F%2F%2F%2Bex%2B3U5vd7s%2Bfq8%2Fs0itq72PMLUPvtAAASvklEQVR4AbXBC0JqCQxEwT5Jd7L%2FHc8FdR4g%2BEGtEr8u%2FBHxu7otdzd%2FQPyqlmRp1Pw%2B8aukDfRa1fw28ZtWy4sa89vEb7LCi0zx28RvqgkvouW3id%2FU8pbtWmv5beJXRWNrRmp%2BnfhlHXZm%2BQPi95Vk%2FoD4fZbMHxC%2FryTzB8Tva435A%2BL3rcb8AfH7VjJ%2FQPy%2BHYk%2FIH5facwfEL8iaZcrnKyn%2BAPi57K2VL2WF1hJ%2FAHxQ2tJrg6HteXVjPkD4ge6V3J1%2BF97zhx%2BnXhWb8nacKXlnYPErxNPyfqw4ZYKVuUZdfhd4hmxunY73NICgfWMOvwm8ZQ1pMvlDZdaCic98kjV4beIp8ScpLvsSvhflzqQmqVLB281v0E8pc2bdNne8EayNTPNSbt02PBj4intcKltb%2FNibY%2BLf9aSO%2FyMeMo6XMva3g0vwrWsxvyMeEoc3knZ2g53ZaXa8DzxlHa4J23Jae5aycXTxFPa4WRdXAtdsivckZXG4TniKWtOSlre6y7LG651Wxq5OzxDPGUVIKNwX6ekCv%2B0ddglVPMM8ZQ10FJ4LGVvOEuXRl7OqnmGeEor4Ck%2BtnI1ZEvjDa%2FcPEM8ZQVY4RO9VqUlN%2F84PEM8JQ50cUgXH2mrKlyq5RniOQ4vVjPLHdu86OKGi2eIr%2BgNV6JwljmYO6zlbJsbWp4hPtVrjYpLLV7UHIp7rOVkixtaniE%2BU5I2Nc2FKJytZhTuiac5rLnh4hniEzUbDjXhn3g5W0nNA1aAKm7YPEN8bMecrZYLWl70hkcyBay5YfMM8aHI4aR7xAUVHyirOdhAmRsqniE%2BtOKsRjIXtDzmmRGHVmDFDRfPEB%2BJzMmO01xScdYnVRs6vPHMFG9W4ZrMM8RHouWw43DNhlDWiSVZY3nDoWYc3qzDNZlniPe6w4uoOFjcKhPXuJNWyG6VqjSuhm7%2BiZorUfEM8U5J8nKyMw0tcZLwPxdRtTlUcUgVdGlml0uZ4pqKZ4hr5VUnpSXdUgVa4hA5vHERV1Tp9XhdJTWHksYd%2Ftdarql4hrjQiaPiYLclNSeebVYz5o0W7Ghsa9blmlFtx01rxP8yy5XIPEP8L1W7bjWHlbzhRTwjzXrCK1f3qqSEyBysLVtayKp40yqurcITxJtUgavVHNob%2FinZTWt5VVvWVKvJSttQCkRjb%2FA4vLK5thOeIN6sm9ai5cTFhYRDy%2FyTGpdU0hxkaZvWUrZluTmLims14QniVbywClqgeouT9IZXNWoupGzNqHa3y5LGVYBnipbCSVxcq1meIN54oRXsbEk26S3NmBcZ807K3gon2ZLcxF5tPMVJprlWE54g3nihtbRHm7WjkbxTHSCWwj1r2U4HSMmdQEmWwonNtah4gnhjA9ZSaohmpnpDjWRptDwS25LcQGsc2Bla5sTFtZV4gnixpWmIVWpgRuVwsiV5q7kv0JJcNVIFapydUrHTQKa5IfMEcRKrurSQ0qhsmVR4kea%2B7pIr9NqSrRltWlaxomUgVVyLxBPEYeUGygtszew2KfOBclVpVN2ctCXNidZaaKWmONhc6rKaJwi6xuGkRmWpAkRa7outF9XN%2F7LlmbJmpiCyvBxk%2FtnSqHmGWGk5i2ZcaWBLau5KKHt3Ce%2FsaLMz46VG4cTFm%2FaMOzxFUYWztjzhkNI43JPyYvPAegPxzFRpOYmWF1WywrPUag5xjRapqqxxubijvYFVaC%2Fv7YSDpzxjzlbhpKXxhqcpWshqtECk0Yys6m5utZdD1LCuCifhfyVOapqsxhyiQMmSm58QNdZheZGV5FqwueXiZBUga28DvRte1NQCpQVSUkFqPbIr%2FIxg7arwJqqEg6e5Vuas1Zytyw1ka5uT9ajKI87WbksaLT8mbkXFyWqaa2rOVuFVStUNpGrDoSTPmDfWdlby8kPiHQtoa0vLpXU4WzX%2FS5W2gWxtOHQ24U3CSUmu8BPinR2XVSFyuNAOZ9Fyae1qDu2qcF8suRKeJt7pcW1zaE9xwcVZq7nWtpeTrQ0PrEeq8CTxnsWrlbThELra5ixqbsXWNoeq6nBft6TlOeK9VnG2lfb4TKOOlpOouKPsWg4pb3Nf1uMGusP3iDtKDaTcgMuWvL1FmZOouCtlbwJs1Yb7SuN2Nd8k7mgvXV4OKWALiGkVJ14eyPqQQG9Vc0dWGnn5LnFPTW1z1gW0OdSyag5aHsvaroVs1YZL2dKMt1nzXeKulas52QLanGy3xq4a87Eu2yHZ2uZNWzPjDbDmu8R9a8m7iQNscbKyy%2BWS%2BUzWtqp7qzpA1jPj8KKK7xIPZG2NVWTTSbpKbs5cfEF6y64qV6ctqcKbdvgm8VhSlnWwJbuaV3LzRb11onFt%2BKcVvkl8one7u3bD%2FzJuXnRt%2BFTXVHOWqubQ4rvEEyI1L1Z2h8%2B0eRHLKiBqvkk8IePmxZq1lk%2B0w0nJUHKIlm8ST8ioeVEFtFwbPhA3h8gcdpZV803iCRkVL7Y42bK2w0NlDqXlpJRV803iGZYrnFRxlqwO3eEuN4dSOGlVme8Sz7C37QZqeZPekl0b3nMBreKsp1bNN4lnWIEtF1Vc6i1bVZtwxQX0NC9UrfBN4hk7zaHLNrey1kgVLljATnO2rmj5JvEMqzlrF%2B%2BFXitcsAArnFkdLd8knrFqPmFzyQq0xUm0tJZvEs8oAR0eix0u1ARSqg70NNHyTeIZUqgZ85gdLlgcMjOSRlBqvkk8wwOSp3moJlyoCYfeKkmBVvgm8YyaUJJ5zOJSTXMWSgus%2BC7xjJpA%2BMiquVATXiUcSuGbxDNqmk%2BUxtW82WmurMI3iWd4wifaHo1rNxx2miul8E3iGTXhc4nH0lQ1O80VK3yTeEYNX5SspbEnXFmFbxLPqGm%2BrsvWFFdK4ZvEM2rCt6RmzCWL7xLP2Anfs2M3Fyy%2BSzyjpvmqDoed5YrFd4ln7DRftHI19BRXSuGbxDN6wtdEqjF4lisS3yWeEYUvWlkDNeZKTfgm8ZFu7mqFr%2FKMYae4lFH4JvGBVLgraghf09uQMZdabr5JfKC2q1zV3IgarOLLPMWllptvEo%2B1e7dkq5ZrLkip%2BKqa4lLk5ZvEY15INay9XIqXVGS%2BqsdcirzclY
D/ContactsSyncAdapter( 9855): getServerDiffs failed
D/ContactsSyncAdapter( 9855): com.google.wireless.gdata2.parser.ParseException: unparsable feed https://www.google.com/m8/feeds/groups/email@google.co.uk/base2_property-android
D/ContactsSyncAdapter( 9855):	at com.google.android.syncadapters.contacts.ContactsSyncAdapter.getServerDiffs(ContactsSyncAdapter.java:1228)
D/ContactsSyncAdapter( 9855):	at com.google.android.syncadapters.contacts.ContactsSyncAdapter.innerPerformSync(ContactsSyncAdapter.java:298)
D/ContactsSyncAdapter( 9855):	at com.google.android.syncadapters.contacts.ContactsSyncAdapter.onPerformLoggedSync(ContactsSyncAdapter.java:176)
D/ContactsSyncAdapter( 9855):	at com.google.android.common.LoggingThreadedSyncAdapter.onPerformSync(LoggingThreadedSyncAdapter.java:33)
D/ContactsSyncAdapter( 9855):	at android.content.AbstractThreadedSyncAdapter$SyncThread.run(AbstractThreadedSyncAdapter.java:254)
D/ContactsSyncAdapter( 9855): FAILURE: processed 0 records in 300 ms from feed https://www.google.com/m8/feeds/groups/email@google.co.uk/base2_property-android, updated time is 2013-08-28T07:57:30.603Z

The first part is (i think) google doing its sync and everything going ok (but deleting my new contact) so no debug is output. I then entered the contact again and manually did a sync and got the second set of debug, where there is a problem with getting the diff list from the server. After which the contact remained, but only until the contact list managed to sync without error.

Extremely annoying! Anyone know a decent avenue to vent my frustration towards some Google support?