--- a/toolkit/components/places/PlacesDBUtils.jsm
+++ b/toolkit/components/places/PlacesDBUtils.jsm
@@ -512,18 +512,30 @@ this.PlacesDBUtils = {
         END`
       },
       { query: `DELETE FROM moz_bm_reindex_temp` },
       { query: `DROP INDEX moz_bm_reindex_temp_index` },
       { query: `DROP TRIGGER moz_bm_reindex_temp_trigger` },
       { query: `DROP TABLE moz_bm_reindex_temp` },
 
       // D.12 Fix empty-named tags.
-      // Tags were allowed to have empty names due to a UI bug.  Fix them
-      // replacing their title with "(notitle)".
+      // Tags were allowed to have empty names due to a UI bug.  Fix them by
+      // replacing their title with "(notitle)", and bumping the change counter
+      // for all bookmarks with the fixed tags.
+      { query:
+        `UPDATE moz_bookmarks SET syncChangeCounter = syncChangeCounter + 1
+         WHERE fk IN (SELECT b.fk FROM moz_bookmarks b
+                      JOIN moz_bookmarks p ON p.id = b.parent
+                      WHERE length(p.title) = 0 AND p.type = :folder_type AND
+                            p.parent = :tags_folder)`,
+        params: {
+          folder_type: PlacesUtils.bookmarks.TYPE_FOLDER,
+          tags_folder: PlacesUtils.tagsFolderId,
+        },
+      },
       { query:
         `UPDATE moz_bookmarks SET title = :empty_title
         WHERE length(title) = 0 AND type = :folder_type
           AND parent = :tags_folder`,
         params: {
           empty_title: "(notitle)",
           folder_type: PlacesUtils.bookmarks.TYPE_FOLDER,
           tags_folder: PlacesUtils.tagsFolderId,

--- a/toolkit/components/places/tests/unit/test_preventive_maintenance.js
+++ b/toolkit/components/places/tests/unit/test_preventive_maintenance.js
@@ -826,32 +826,39 @@ tests.push({
   }
 });
 
 // ------------------------------------------------------------------------------
 
 tests.push({
   name: "D.12",
   desc: "Fix empty-named tags",
+  _taggedItemIds: {},
 
   setup() {
     // Add a place to ensure place_id = 1 is valid
     let placeId = addPlace();
     // Create a empty-named tag.
     this._untitledTagId = addBookmark(null, bs.TYPE_FOLDER, bs.tagsFolder, null, null, "");
     // Insert a bookmark in the tag, otherwise it will be removed.
     addBookmark(placeId, bs.TYPE_BOOKMARK, this._untitledTagId);
     // Create a empty-named folder.
     this._untitledFolderId = addBookmark(null, bs.TYPE_FOLDER, bs.toolbarFolder, null, null, "");
     // Create a titled tag.
     this._titledTagId = addBookmark(null, bs.TYPE_FOLDER, bs.tagsFolder, null, null, "titledTag");
     // Insert a bookmark in the tag, otherwise it will be removed.
     addBookmark(placeId, bs.TYPE_BOOKMARK, this._titledTagId);
     // Create a titled folder.
     this._titledFolderId = addBookmark(null, bs.TYPE_FOLDER, bs.toolbarFolder, null, null, "titledFolder");
+
+    // Create two tagged bookmarks in different folders.
+    this._taggedItemIds.inMenu = addBookmark(placeId, bs.TYPE_BOOKMARK,
+      bs.bookmarksMenuFolder, null, null, "Tagged bookmark in menu");
+    this._taggedItemIds.inToolbar = addBookmark(placeId, bs.TYPE_BOOKMARK,
+      bs.toolbarFolder, null, null, "Tagged bookmark in toolbar");
   },
 
   check() {
     // Check that valid bookmark is still there
     let stmt = mDBConn.createStatement(
       "SELECT title FROM moz_bookmarks WHERE id = :id"
     );
     stmt.params.id = this._untitledTagId;
@@ -865,16 +872,26 @@ tests.push({
     stmt.params.id = this._titledTagId;
     Assert.ok(stmt.executeStep());
     Assert.equal(stmt.row.title, "titledTag");
     stmt.reset();
     stmt.params.id = this._titledFolderId;
     Assert.ok(stmt.executeStep());
     Assert.equal(stmt.row.title, "titledFolder");
     stmt.finalize();
+
+    let taggedItemsStmt = mDBConn.createStatement(`
+      SELECT syncChangeCounter FROM moz_bookmarks
+      WHERE id IN (:taggedInMenu, :taggedInToolbar)`);
+    taggedItemsStmt.params.taggedInMenu = this._taggedItemIds.inMenu;
+    taggedItemsStmt.params.taggedInToolbar = this._taggedItemIds.inToolbar;
+    while (taggedItemsStmt.executeStep()) {
+      Assert.greaterOrEqual(taggedItemsStmt.row.syncChangeCounter, 1);
+    }
+    taggedItemsStmt.finalize();
   }
 });
 
 // ------------------------------------------------------------------------------
 
 tests.push({
   name: "E.1",
   desc: "Remove orphan icon entries",