--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -470,19 +470,19 @@ BookmarksEngine.prototype = {
       delete this._guidMap;
       return this._guidMap = guidMap;
     });
 
     this._store._childrenToOrder = {};
     this._store.clearPendingDeletions();
   },
 
-  _deletePending() {
+  async _deletePending() {
     // Delete pending items -- See the comment above BookmarkStore's deletePending
-    let newlyModified = Async.promiseSpinningly(this._store.deletePending());
+    let newlyModified = await this._store.deletePending();
     if (newlyModified) {
       this._log.debug("Deleted pending items", newlyModified);
       this._modified.insert(newlyModified);
     }
   },
 
   _shouldReviveRemotelyDeletedRecord(item) {
     let modifiedTimestamp = this._modified.getModifiedTimestamp(item.id);
@@ -501,27 +501,33 @@ BookmarksEngine.prototype = {
     if (newChanges) {
       this._modified.insert(newChanges);
       return true;
     }
     return false;
   },
 
   _processIncoming(newitems) {
-    try {
-      SyncEngine.prototype._processIncoming.call(this, newitems);
-    } finally {
-      try {
-        this._deletePending();
-      } finally {
-        // Reorder children.
-        this._store._orderChildren();
-        delete this._store._childrenToOrder;
-      }
-    }
+    SyncEngine.prototype._processIncoming.call(this, newitems);
+    Async.promiseSpinningly(this._postProcessIncoming());
+  },
+
+  // Applies pending tombstones, sets folder child order, and updates the sync
+  // status of all `NEW` bookmarks to `NORMAL`.
+  async _postProcessIncoming() {
+    await this._deletePending();
+    await this._orderChildren();
+
+    let changes = this._modified.changes;
+    await PlacesSyncUtils.bookmarks.markChangesAsSyncing(changes);
+  },
+
+  async _orderChildren() {
+    await this._store._orderChildren();
+    this._store._childrenToOrder = {};
   },
 
   _syncFinish: function _syncFinish() {
     SyncEngine.prototype._syncFinish.call(this);
     this._tracker._ensureMobileQuery();
   },
 
   _syncCleanup: function _syncCleanup() {
@@ -729,24 +735,25 @@ BookmarksStore.prototype = {
       this._log.debug(`Updated ${item.kind} ${item.syncId} under ${
         item.parentSyncId}`, item);
       if (item.dateAdded != record.dateAdded) {
         this.engine._needWeakReupload.add(item.syncId);
       }
     }
   },
 
-  _orderChildren: function _orderChildren() {
-    let promises = Object.keys(this._childrenToOrder).map(syncID => {
+  async _orderChildren() {
+    for (let syncID in this._childrenToOrder) {
       let children = this._childrenToOrder[syncID];
-      return PlacesSyncUtils.bookmarks.order(syncID, children).catch(ex => {
+      try {
+        await PlacesSyncUtils.bookmarks.order(syncID, children);
+      } catch (ex) {
         this._log.debug(`Could not order children for ${syncID}`, ex);
-      });
-    });
-    Async.promiseSpinningly(Promise.all(promises));
+      }
+    }
   },
 
   // There's some complexity here around pending deletions. Our goals:
   //
   // - Don't delete any bookmarks a user has created but not explicitly deleted
   //   (This includes any bookmark that was not a child of the folder at the
   //   time the deletion was recorded, and also bookmarks restored from a backup).
   // - Don't undelete any bookmark without ensuring the server structure
@@ -1195,17 +1202,19 @@ class BookmarksChangeset extends Changes
     super.changeID(oldID, newID);
     this.weakChanges[newID] = this.weakChanges[oldID];
     delete this.weakChanges[oldID];
   }
 
   ids() {
     let results = new Set();
     for (let id in this.changes) {
-      results.add(id);
+      if (!this.changes[id].synced) {
+        results.add(id);
+      }
     }
     for (let id in this.weakChanges) {
       results.add(id);
     }
     return [...results];
   }
 
   clear() {

--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -331,19 +331,27 @@ const BookmarkSyncUtils = PlacesSyncUtil
    * can recover correctly after an interrupted sync.
    *
    * @return {Promise} resolved once all items have been fetched.
    * @resolves to an object containing records for changed bookmarks, keyed by
    *           the sync ID.
    * @see pullSyncChanges for the implementation, and markChangesAsSyncing for
    *      an explanation of why we update the sync status.
    */
-  pullChanges() {
-    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: pullChanges",
-      db => pullSyncChanges(db));
+  async pullChanges() {
+    let db = await PlacesUtils.promiseDBConnection();
+    return pullSyncChanges(db);
+  },
+
+  /**
+   * ...
+   */
+  markChangesAsSyncing(changeRecords) {
+    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: markChangesAsSyncing",
+      db => markChangesAsSyncing(db, changeRecords));
   },
 
   /**
    * Decrements the sync change counter, updates the sync status, and cleans up
    * tombstones for successfully synced items. Sync calls this method at the
    * end of each bookmark sync.
    *
    * @param changeRecords
@@ -468,18 +476,18 @@ const BookmarkSyncUtils = PlacesSyncUtil
       if (wasRemoved) {
         BookmarkSyncLog.trace(`remove: Removed folder ${bookmarkItem.guid}`);
       }
     }
 
     // TODO (Bug 1313890): Refactor the bookmarks engine to pull change records
     // before uploading, instead of returning records to merge into the engine's
     // initial changeset.
-    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: remove",
-      db => pullSyncChanges(db));
+    let db = yield PlacesUtils.promiseDBConnection();
+    return pullSyncChanges(db);
   }),
 
   /**
    * Increments the change counter of a non-folder item and its parent. Sync
    * calls this method to override a remote deletion for an item that's changed
    * locally.
    *
    * @param syncId
@@ -1738,18 +1746,16 @@ var pullSyncChanges = Task.async(functio
     WHERE syncChangeCounter >= 1
     UNION ALL
     SELECT guid, dateRemoved AS modified, 1 AS syncChangeCounter,
            :deletedSyncStatus, 1 AS tombstone
     FROM moz_bookmarks_deleted`,
     { deletedSyncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL },
     row => addRowToChangeRecords(row, changeRecords));
 
-  yield markChangesAsSyncing(db, changeRecords);
-
   return changeRecords;
 });
 
 var touchSyncBookmark = Task.async(function* (db, bookmarkItem) {
   if (BookmarkSyncLog.level <= Log.Level.Trace) {
     BookmarkSyncLog.trace(
       `touch: Reviving item "${bookmarkItem.guid}" and marking parent ` +
       BookmarkSyncUtils.guidToSyncId(bookmarkItem.parentGuid) + ` as modified`);