--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -244,16 +244,27 @@ BookmarksEngine.prototype = {
     this._store.changeItemID(dupeId, item.id);
     this._deleteId(dupeId);
     this._tracker.addChangedID(item.id, 0);
   }
 };
 
 function BookmarksStore(name) {
   Store.call(this, name);
+
+  // Explicitly nullify our references to our cached services so we don't leak
+  Observers.add("places-shutdown", function() {
+    this.__bms = null;
+    this.__hsvc = null;
+    this.__ls = null;
+    this.__ms = null;
+    this.__ts = null;
+    if (this.__frecencyStm)
+      this.__frecencyStm.finalize();
+  }, this);
 }
 BookmarksStore.prototype = {
   __proto__: Store.prototype,
 
   __bms: null,
   get _bms() {
     if (!this.__bms)
       this.__bms = Cc["@mozilla.org/browser/nav-bookmarks-service;1"].
@@ -268,32 +279,34 @@ BookmarksStore.prototype = {
                     getService(Ci.nsINavHistoryService);
     return this.__hsvc;
   },
 
   __ls: null,
   get _ls() {
     if (!this.__ls)
       this.__ls = Cc["@mozilla.org/browser/livemark-service;2"].
-        getService(Ci.nsILivemarkService);
+                  getService(Ci.nsILivemarkService);
     return this.__ls;
   },
 
+  __ms: null,
   get _ms() {
-    let ms;
-    try {
-      ms = Cc["@mozilla.org/microsummary/service;1"].
-        getService(Ci.nsIMicrosummaryService);
-    } catch (e) {
-      ms = null;
-      this._log.warn("Could not load microsummary service");
-      this._log.debug(e);
+    if (!this.__ms) {
+      try {
+        this.__ms = Cc["@mozilla.org/microsummary/service;1"].
+                    getService(Ci.nsIMicrosummaryService);
+      } catch (e) {
+        this._log.warn("Could not load microsummary service");
+        this._log.debug(e);
+        // Redefine our getter so we won't keep trying to get the service
+        this.__defineGetter__("_ms", function() null);
+      }
     }
-    this.__defineGetter__("_ms", function() ms);
-    return ms;
+    return this.__ms;
   },
 
   __ts: null,
   get _ts() {
     if (!this.__ts)
       this.__ts = Cc["@mozilla.org/browser/tagging-service;1"].
                   getService(Ci.nsITaggingService);
     return this.__ts;
@@ -830,24 +843,26 @@ BookmarksStore.prototype = {
 
     record.parentid = this._getParentGUIDForId(placeId);
     record.predecessorid = this._getPredecessorGUIDForId(placeId);
     record.sortindex = this._calculateIndex(record);
 
     return record;
   },
 
+  __frecencyStm: null,
   get _frecencyStm() {
-    this._log.trace("Creating SQL statement: _frecencyStm");
-    let stm = Svc.History.DBConnection.createStatement(
-      "SELECT frecency " +
-      "FROM moz_places " +
-      "WHERE url = :url");
-    this.__defineGetter__("_frecencyStm", function() stm);
-    return stm;
+    if (!this.__frecencyStm) {
+      this._log.trace("Creating SQL statement: _frecencyStm");
+      this.__frecencyStm = Svc.History.DBConnection.createStatement(
+        "SELECT frecency " +
+        "FROM moz_places " +
+        "WHERE url = :url");
+    }
+    return this.__frecencyStm;
   },
 
   _calculateIndex: function _calculateIndex(record) {
     // For anything directly under the toolbar, give it a boost of more than an
     // unvisited bookmark
     let index = 0;
     if (record.parentid == "toolbar")
       index += 150;
@@ -982,32 +997,40 @@ BookmarksStore.prototype = {
 function BookmarksTracker(name) {
   Tracker.call(this, name);
 
   // Ignore changes to the special roots
   for (let guid in kSpecialIds)
     this.ignoreID(guid);
 
   Svc.Bookmark.addObserver(this, false);
+
+  // Explicitly nullify our references to our cached services so we don't leak
+  Observers.add("places-shutdown", function() {
+    this.__ls = null;
+    this.__bms = null;
+  }, this);
 }
 BookmarksTracker.prototype = {
   __proto__: Tracker.prototype,
 
+  __bms: null,
   get _bms() {
-    let bms = Cc["@mozilla.org/browser/nav-bookmarks-service;1"].
-      getService(Ci.nsINavBookmarksService);
-    this.__defineGetter__("_bms", function() bms);
-    return bms;
+    if (!this.__bms)
+      this.__bms = Cc["@mozilla.org/browser/nav-bookmarks-service;1"].
+                   getService(Ci.nsINavBookmarksService);
+    return this.__bms;
   },
 
+  __ls: null,
   get _ls() {
-    let ls = Cc["@mozilla.org/browser/livemark-service;2"].
-      getService(Ci.nsILivemarkService);
-    this.__defineGetter__("_ls", function() ls);
-    return ls;
+    if (!this.__ls)
+      this.__ls = Cc["@mozilla.org/browser/livemark-service;2"].
+                  getService(Ci.nsILivemarkService);
+    return this.__ls;
   },
 
   QueryInterface: XPCOMUtils.generateQI([
     Ci.nsINavBookmarkObserver,
     Ci.nsINavBookmarkObserver_MOZILLA_1_9_1_ADDITIONS
   ]),
 
   /**

--- a/services/sync/tests/unit/test_bookmark_order.js
+++ b/services/sync/tests/unit/test_bookmark_order.js
@@ -34,19 +34,16 @@ function check(expected) {
   let bookmarks = getBookmarks(Svc.Bookmark.unfiledBookmarksFolder);
 
   _("Checking if the bookmark structure is", JSON.stringify(expected));
   _("Got bookmarks:", JSON.stringify(bookmarks));
   do_check_true(Utils.deepEquals(bookmarks, expected));
 }
 
 function run_test() {
-  //XXXzpao test is disabled (bug 583985)
-  return;
-
   _("Starting with a clean slate of no bookmarks");
   let store = new (new BookmarksEngine())._storeObj();
   store.wipe();
   check([]);
 
   function $B(name, parent, pred) {
     let bookmark = new Bookmark();
     bookmark.id = name;

--- a/services/sync/tests/unit/test_bookmark_predecessor.js
+++ b/services/sync/tests/unit/test_bookmark_predecessor.js
@@ -1,16 +1,13 @@
 _("Make sure bad bookmarks can still get their predecessors");
 Cu.import("resource://services-sync/engines/bookmarks.js");
 Cu.import("resource://services-sync/util.js");
 
 function run_test() {
-  //XXXzpao test is disabled (bug 583985)
-  return;
-
   _("Starting with a clean slate of no bookmarks");
   let store = new (new BookmarksEngine())._storeObj();
   store.wipe();
 
   let uri = Utils.makeURI("http://uri/");
   function insert(pos, folder) {
     folder = folder || Svc.Bookmark.toolbarFolder;
     let name = "pos" + pos;