--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -905,43 +905,49 @@ var insertSyncLivemark = Task.async(func
 // (the postData is not synced, so we ignore it). Sync associates keywords with
 // bookmarks, which is not really accurate. -- We might already have a keyword
 // with that name, or we might already have another bookmark with that URL with
 // a different keyword, etc.
 //
 // If we don't handle those cases by removing the conflicting keywords first,
 // the insertion  will fail, and the keywords will either be wrong, or missing.
 // This function handles those cases.
-var removeConflictingKeywords = Task.async(function* (bookmarkURL, newKeyword) {
-  let entryForURL = yield PlacesUtils.keywords.fetch({
-    url: bookmarkURL
-  });
-  if (entryForURL && entryForURL.keyword !== newKeyword) {
-    yield PlacesUtils.keywords.remove({
-      keyword: entryForURL.keyword,
-      source: SOURCE_SYNC,
-    });
-    // This will cause us to reupload this record for this sync, but without it,
-    // we will risk data corruption.
-    yield BookmarkSyncUtils.addSyncChangesForBookmarksWithURL(entryForURL.url.href);
-  }
-  if (!newKeyword) {
-    return;
-  }
-  let entryForNewKeyword = yield PlacesUtils.keywords.fetch({
-    keyword: newKeyword
-  });
-  if (entryForNewKeyword) {
-    yield PlacesUtils.keywords.remove({
-      keyword: entryForNewKeyword.keyword,
-      source: SOURCE_SYNC,
-    });
-    yield BookmarkSyncUtils.addSyncChangesForBookmarksWithURL(entryForNewKeyword.url.href);
-  }
-});
+function removeConflictingKeywords(bookmarkURL, newKeyword) {
+  return PlacesUtils.withConnectionWrapper(
+    "BookmarkSyncUtils: removeConflictingKeywords", Task.async(function* (db) {
+      let entryForURL = yield PlacesUtils.keywords.fetch({
+        url: bookmarkURL.href,
+      });
+      if (entryForURL && entryForURL.keyword !== newKeyword) {
+        yield PlacesUtils.keywords.remove({
+          keyword: entryForURL.keyword,
+          source: SOURCE_SYNC,
+        });
+        // This will cause us to reupload this record for this sync, but without it,
+        // we will risk data corruption.
+        yield BookmarkSyncUtils.addSyncChangesForBookmarksWithURL(
+          db, entryForURL.url, 1);
+      }
+      if (!newKeyword) {
+        return;
+      }
+      let entryForNewKeyword = yield PlacesUtils.keywords.fetch({
+        keyword: newKeyword
+      });
+      if (entryForNewKeyword) {
+        yield PlacesUtils.keywords.remove({
+          keyword: entryForNewKeyword.keyword,
+          source: SOURCE_SYNC,
+        });
+        yield BookmarkSyncUtils.addSyncChangesForBookmarksWithURL(
+          db, entryForNewKeyword.url, 1);
+      }
+    })
+  );
+}
 
 // Sets annotations, keywords, and tags on a new bookmark. Returns a Sync
 // bookmark object.
 var insertBookmarkMetadata = Task.async(function* (bookmarkItem, insertInfo) {
   let itemId = yield PlacesUtils.promiseItemId(bookmarkItem.guid);
   let newItem = yield placesBookmarkToSyncBookmark(bookmarkItem);
 
   if (insertInfo.query) {
@@ -955,17 +961,17 @@ var insertBookmarkMetadata = Task.async(
   try {
     newItem.tags = yield tagItem(bookmarkItem, insertInfo.tags);
   } catch (ex) {
     BookmarkSyncLog.warn(`insertBookmarkMetadata: Error tagging item ${
       insertInfo.syncId}`, ex);
   }
 
   if (insertInfo.keyword) {
-    yield removeConflictingKeywords(bookmarkItem.url.href, insertInfo.keyword);
+    yield removeConflictingKeywords(bookmarkItem.url, insertInfo.keyword);
     yield PlacesUtils.keywords.insert({
       keyword: insertInfo.keyword,
       url: bookmarkItem.url.href,
       source: SOURCE_SYNC,
     });
     newItem.keyword = insertInfo.keyword;
   }
 
@@ -1169,17 +1175,17 @@ var updateBookmarkMetadata = Task.async(
     newItem.tags = yield tagItem(newBookmarkItem, updateInfo.tags);
   } catch (ex) {
     BookmarkSyncLog.warn(`updateBookmarkMetadata: Error tagging item ${
       updateInfo.syncId}`, ex);
   }
 
   if (updateInfo.hasOwnProperty("keyword")) {
     // Unconditionally remove the old keyword.
-    yield removeConflictingKeywords(oldBookmarkItem.url.href, updateInfo.keyword);
+    yield removeConflictingKeywords(oldBookmarkItem.url, updateInfo.keyword);
     if (updateInfo.keyword) {
       yield PlacesUtils.keywords.insert({
         keyword: updateInfo.keyword,
         url: newItem.url.href,
         source: SOURCE_SYNC,
       });
     }
     newItem.keyword = updateInfo.keyword;

--- a/toolkit/components/places/tests/unit/test_sync_utils.js
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -710,16 +710,98 @@ add_task(function* test_update_keyword()
     equal(updatedItem.keyword, "test4", "Initial item still has keyword");
   }
 
 
   yield PlacesUtils.bookmarks.eraseEverything();
   yield PlacesSyncUtils.bookmarks.reset();
 });
 
+add_task(function* test_conflicting_keywords() {
+  yield ignoreChangedRoots();
+
+  do_print("Insert bookmark with new keyword");
+  let tbBmk = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: "unfiled",
+    url: "http://getthunderbird.com",
+    keyword: "tbird",
+  });
+  {
+    let entryByKeyword = yield PlacesUtils.keywords.fetch("tbird");
+    equal(entryByKeyword.url.href, "http://getthunderbird.com/",
+      "Should return new keyword entry by URL");
+    let entryByURL = yield PlacesUtils.keywords.fetch({
+      url: "http://getthunderbird.com",
+    });
+    equal(entryByURL.keyword, "tbird", "Should return new entry by keyword");
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(changes, {},
+      "Should not bump change counter for new keyword entry");
+  }
+
+  do_print("Insert bookmark with same URL and different keyword");
+  let dupeTbBmk = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: "toolbar",
+    url: "http://getthunderbird.com",
+    keyword: "tb",
+  });
+  {
+    let oldKeywordByURL = yield PlacesUtils.keywords.fetch("tbird");
+    ok(!oldKeywordByURL,
+      "Should remove old entry when inserting bookmark with different keyword");
+    let entryByKeyword = yield PlacesUtils.keywords.fetch("tb");
+    equal(entryByKeyword.url.href, "http://getthunderbird.com/",
+      "Should return different keyword entry by URL");
+    let entryByURL = yield PlacesUtils.keywords.fetch({
+      url: "http://getthunderbird.com",
+    });
+    equal(entryByURL.keyword, "tb", "Should return different entry by keyword");
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(), [
+      tbBmk.syncId,
+      dupeTbBmk.syncId,
+    ].sort(), "Should bump change counter for bookmarks with different keyword");
+    yield setChangesSynced(changes);
+  }
+
+  do_print("Update bookmark with different keyword");
+  yield PlacesSyncUtils.bookmarks.update({
+    kind: "bookmark",
+    syncId: tbBmk.syncId,
+    url: "http://getthunderbird.com",
+    keyword: "thunderbird",
+  });
+  {
+    let oldKeywordByURL = yield PlacesUtils.keywords.fetch("tb");
+    ok(!oldKeywordByURL,
+      "Should remove old entry when updating bookmark keyword");
+    let entryByKeyword = yield PlacesUtils.keywords.fetch("thunderbird");
+    equal(entryByKeyword.url.href, "http://getthunderbird.com/",
+      "Should return updated keyword entry by URL");
+    let entryByURL = yield PlacesUtils.keywords.fetch({
+      url: "http://getthunderbird.com",
+    });
+    equal(entryByURL.keyword, "thunderbird",
+      "Should return entry by updated keyword");
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(), [
+      tbBmk.syncId,
+      dupeTbBmk.syncId,
+    ].sort(), "Should bump change counter for bookmarks with updated keyword");
+    yield setChangesSynced(changes);
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});
+
 add_task(function* test_update_annos() {
   let guids = yield populateTree(PlacesUtils.bookmarks.menuGuid, {
     kind: "folder",
     title: "folder",
   }, {
     kind: "bookmark",
     title: "bmk",
     url: "https://example.com",