--- a/services/sync/modules/bookmark_validator.js
+++ b/services/sync/modules/bookmark_validator.js
@@ -224,24 +224,31 @@ XPCOMUtils.defineLazyGetter(this, "SYNCE
 ]);
 
 class BookmarkValidator {
 
   async canValidate() {
     return !await PlacesSyncUtils.bookmarks.havePendingChanges();
   }
 
-  _followQueries(recordMap) {
+  async _followQueries(recordMap) {
     for (let [guid, entry] of recordMap) {
       if (entry.type !== "query" && (!entry.bmkUri || !entry.bmkUri.startsWith(QUERY_PROTOCOL))) {
         continue;
       }
       // Might be worth trying to parse the place: query instead so that this
       // works "automatically" with things like aboutsync.
-      let queryNodeParent = PlacesUtils.getFolderContents(entry, false, true);
+      let id;
+      try {
+        id = await PlacesUtils.promiseItemId(guid);
+      } catch (ex) {
+        // guid isn't found, so this doesn't exist locally.
+        continue;
+      }
+      let queryNodeParent = PlacesUtils.getFolderContents(id, false, true);
       if (!queryNodeParent || !queryNodeParent.root.hasChildren) {
         continue;
       }
       queryNodeParent = queryNodeParent.root;
       let queryNode = null;
       let numSiblings = 0;
       let containerWasOpen = queryNodeParent.containerOpen;
       queryNodeParent.containerOpen = true;
@@ -352,17 +359,17 @@ class BookmarkValidator {
           child.parent = treeNode;
           child.parentid = guid;
           treeNode.childGUIDs.push(child.guid);
         }
       }
     }
     await traverse(clientTree, false);
     clientTree.id = "places";
-    this._followQueries(recordsByGuid);
+    await this._followQueries(recordsByGuid);
     return records;
   }
 
   /**
    * Process the server-side list. Mainly this builds the records into a tree,
    * but it also records information about problems, and produces arrays of the
    * deleted and non-deleted nodes.
    *