I have an idea what the reason could be: findNew() creates remote file name and UID when a record is synced the first time. When this first sync where findNew() returns the new items suceeds, everything is OK.
However, when the sync does not succeed, maybe the contacts data provider takes the records as “updated” (because of the generated UID and remote file name fields) instead of “new”. This would explain why the resource is uploaded as “updated” record instead of a “new” record, causing the upload to fail (because on the remote server, the record doesn’t exist yet, so the update fails).