--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -896,16 +896,53 @@ var insertSyncLivemark = Task.async(func
     return null;
   }
 
   let livemarkItem = yield PlacesUtils.livemarks.addLivemark(livemarkInfo);
 
   return insertBookmarkMetadata(livemarkItem, insertInfo);
 });
 
+// Keywords are a 1 to 1 mapping between strings and pairs of (URL, postData).
+// (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);
+  }
+});
+
 // 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) {
     PlacesUtils.annotations.setItemAnnotation(itemId,
@@ -918,16 +955,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 PlacesUtils.keywords.insert({
       keyword: insertInfo.keyword,
       url: bookmarkItem.url.href,
       source: SOURCE_SYNC,
     });
     newItem.keyword = insertInfo.keyword;
   }
 
@@ -1131,25 +1169,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.
-    let entry = yield PlacesUtils.keywords.fetch({
-      url: oldBookmarkItem.url.href,
-    });
-    if (entry) {
-      yield PlacesUtils.keywords.remove({
-        keyword: entry.keyword,
-        source: SOURCE_SYNC,
-      });
-    }
+    yield removeConflictingKeywords(oldBookmarkItem.url.href, 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
@@ -614,16 +614,108 @@ add_task(function* test_update_keyword()
     });
     let entry = yield PlacesUtils.keywords.fetch({
       url: "https://mozilla.org",
     });
     ok(!entry,
       "Removing keyword for URL without existing keyword should succeed");
   }
 
+  let item2;
+  do_print("Insert removes other item's keyword if they are the same");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      syncId: item.syncId,
+      keyword: "test",
+    });
+    equal(updatedItem.keyword, "test", "Initial update succeeds");
+    item2 = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "bookmark",
+      parentSyncId: "menu",
+      url: "https://mozilla.org/1",
+      syncId: makeGuid(),
+      keyword: "test",
+    });
+    equal(item2.keyword, "test", "insert with existing should succeed");
+    updatedItem = yield PlacesSyncUtils.bookmarks.fetch(item.syncId);
+    ok(!updatedItem.keyword, "initial item no longer has keyword");
+    let entry = yield PlacesUtils.keywords.fetch({
+      url: "https://mozilla.org",
+    });
+    ok(!entry, "Direct check for original url keyword gives nothing");
+    let newEntry = yield PlacesUtils.keywords.fetch("test");
+    ok(newEntry, "Keyword should exist for new item");
+    equal(newEntry.url.href, "https://mozilla.org/1", "Keyword should point to new url");
+  }
+
+  do_print("Insert updates other item's keyword if they are the same url");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      syncId: item.syncId,
+      keyword: "test2",
+    });
+    equal(updatedItem.keyword, "test2", "Initial update succeeds");
+    let newItem = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "bookmark",
+      parentSyncId: "menu",
+      url: "https://mozilla.org",
+      syncId: makeGuid(),
+      keyword: "test3",
+    });
+    equal(newItem.keyword, "test3", "insert with existing should succeed");
+    updatedItem = yield PlacesSyncUtils.bookmarks.fetch(item.syncId);
+    equal(updatedItem.keyword, "test3", "initial item has new keyword");
+  }
+
+  do_print("Update removes other item's keyword if they are the same");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      syncId: item.syncId,
+      keyword: "test4",
+    });
+    equal(updatedItem.keyword, "test4", "Initial update succeeds");
+    let updatedItem2 = yield PlacesSyncUtils.bookmarks.update({
+      syncId: item2.syncId,
+      keyword: "test4",
+    });
+    equal(updatedItem2.keyword, "test4", "New update succeeds");
+    updatedItem = yield PlacesSyncUtils.bookmarks.fetch(item.syncId);
+    ok(!updatedItem.keyword, "initial item no longer has keyword");
+    let entry = yield PlacesUtils.keywords.fetch({
+      url: "https://mozilla.org",
+    });
+    ok(!entry, "Direct check for original url keyword gives nothing");
+    let newEntry = yield PlacesUtils.keywords.fetch("test4");
+    ok(newEntry, "Keyword should exist for new item");
+    equal(newEntry.url.href, "https://mozilla.org/1", "Keyword should point to new url");
+  }
+
+  do_print("Update url updates it's keyword if url already has keyword");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      syncId: item.syncId,
+      keyword: "test4",
+    });
+    equal(updatedItem.keyword, "test4", "Initial update succeeds");
+    let updatedItem2 = yield PlacesSyncUtils.bookmarks.update({
+      syncId: item2.syncId,
+      keyword: "test5",
+    });
+    equal(updatedItem2.keyword, "test5", "New update succeeds");
+    yield PlacesSyncUtils.bookmarks.update({
+      syncId: item2.syncId,
+      url: item.url.href,
+    });
+    updatedItem2 = yield PlacesSyncUtils.bookmarks.fetch(item2.syncId);
+    equal(updatedItem2.keyword, "test4", "Item keyword has been updated");
+    updatedItem = yield PlacesSyncUtils.bookmarks.fetch(item.syncId);
+    equal(updatedItem.keyword, "test4", "Initial item still has keyword");
+  }
+
+
   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",