--- a/toolkit/components/extensions/ExtensionStorageSync.jsm
+++ b/toolkit/components/extensions/ExtensionStorageSync.jsm
@@ -208,17 +208,17 @@ if (AppConstants.platform != "android") 
       const cryptoKeyRecord = yield collection.getAny(STORAGE_SYNC_CRYPTO_KEYRING_RECORD_ID);
 
       let data = cryptoKeyRecord.data;
       if (!data) {
         // This is a new keyring. Invent an ID for this record. If this
         // changes, it means a client replaced the keyring, so we need to
         // reupload everything.
         const uuidgen = Cc["@mozilla.org/uuid-generator;1"].getService(Ci.nsIUUIDGenerator);
-        const uuid = uuidgen.generateUUID();
+        const uuid = uuidgen.generateUUID().toString();
         data = {uuid};
       }
       return data;
     }),
 
     /**
      * Retrieve the actual keyring from the crypto collection.
      *
@@ -659,17 +659,17 @@ this.ExtensionStorageSync = {
       // changes is when a new keyring is uploaded, which only happens
       // after a server wipe. So when we get a "conflict" (resolved by
       // server_wins), we check whether the server version has a new
       // UUID. If so, reset our sync status, so that we'll reupload
       // everything.
       const result = yield cryptoCollection.sync();
       if (result.resolved.length > 0) {
         if (result.resolved[0].uuid != cryptoKeyRecord.uuid) {
-          log.info("Detected a new UUID. Reseting sync status for everything.");
+          log.info(`Detected a new UUID (${result.resolved[0].uuid}, was ${cryptoKeyRecord.uuid}). Reseting sync status for everything.`);
           yield cryptoCollection.resetSyncStatus();
 
           // Server version is now correct. Return that result.
           return result;
         }
       }
       // No conflicts, or conflict was just someone else adding keys.
       return result;

--- a/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
+++ b/toolkit/components/extensions/test/xpcshell/test_ext_storage_sync.js
@@ -190,17 +190,24 @@ class KintoServer {
 
       response.setStatusLine(null, 200, "OK");
       response.setHeader("Content-Type", "application/json; charset=UTF-8");
       response.setHeader("Date", (new Date()).toUTCString());
       response.setHeader("ETag", this.etag.toString());
 
       const records = this.collections.get(collectionId);
       // Can't JSON a Set directly, so convert to Array
-      const data = Array.from(records);
+      let data = Array.from(records);
+      if (request.queryString.includes("_since=")) {
+        data = data.filter(r => !(r._inPast || false));
+      }
+
+      // Remove records that we only needed to serve once.
+      // FIXME: come up with a more coherent idea of time here.
+      // See bug 1321570.
       for (const record of records) {
         if (record._onlyOnce) {
           records.delete(record);
         }
       }
 
       const body = JSON.stringify({
         "data": data,
@@ -249,31 +256,52 @@ class KintoServer {
       "last_modified": etag,
     };
     this.etag = etag;
     const methodName = conflict ? "encryptAndAddRecordWithConflict" : "encryptAndAddRecord";
     this[methodName](new KeyRingEncryptionRemoteTransformer(),
                      "storage-sync-crypto", keysRecord);
   }
 
+  // Add an already-encrypted record.
+  addRecord(collectionId, record) {
+    this.collections.get(collectionId).add(record);
+  }
+
+  // Add a record that is only served if no `_since` is present.
+  //
+  // Since in real life, Kinto only serves a record as part of a
+  // changes feed if `_since` is before the record's modification
+  // time, this can be helpful to test certain kinds of syncing logic.
+  //
+  // FIXME: tracking of "time" in this mock server really needs to be
+  // implemented correctly rather than these hacks. See bug 1321570.
+  addRecordInPast(collectionId, record) {
+    record._inPast = true;
+    this.addRecord(collectionId, record);
+  }
+
   encryptAndAddRecord(transformer, collectionId, record) {
     return transformer.encode(record).then(encrypted => {
-      this.collections.get(collectionId).add(encrypted);
+      this.addRecord(collectionId, encrypted);
     });
   }
 
   // Like encryptAndAddRecord, but add a flag that will only serve
   // this record once.
   //
   // Since in real life, Kinto only serves a record as part of a changes feed
   // once, this can be useful for testing complicated syncing logic.
+  //
+  // FIXME: This kind of logic really needs to be subsumed into some
+  // more-realistic tracking of "time" (simulated by etags). See bug 1321570.
   encryptAndAddRecordOnlyOnce(transformer, collectionId, record) {
     return transformer.encode(record).then(encrypted => {
       encrypted._onlyOnce = true;
-      this.collections.get(collectionId).add(encrypted);
+      this.addRecord(collectionId, encrypted);
     });
   }
 
   // Conflicts block the next push and then appear in the collection specified.
   encryptAndAddRecordWithConflict(transformer, collectionId, record) {
     return transformer.encode(record).then(encrypted => {
       this.conflicts.push({collectionId, encrypted});
     });
@@ -400,17 +428,17 @@ const loggedInUser = {
       token: "some-access-token",
     },
   },
 };
 const defaultCollectionId = extensionIdToCollectionId(loggedInUser, defaultExtensionId);
 
 function uuid() {
   const uuidgen = Cc["@mozilla.org/uuid-generator;1"].getService(Ci.nsIUUIDGenerator);
-  return uuidgen.generateUUID();
+  return uuidgen.generateUUID().toString();
 }
 
 add_task(function* test_key_to_id() {
   equal(keyToId("foo"), "key-foo");
   equal(keyToId("my-new-key"), "key-my_2D_new_2D_key");
   equal(keyToId(""), "key-");
   equal(keyToId("™"), "key-_2122_");
   equal(keyToId("\b"), "key-_8_");
@@ -458,16 +486,39 @@ add_task(function* ensureKeysFor_posts_n
       ok(newKeys.hasKeysFor([extensionId]), `key isn't present for ${extensionId}`);
 
       let posts = server.getPosts();
       equal(posts.length, 1);
       const post = posts[0];
       assertPostedNewRecord(post);
       const body = yield assertPostedEncryptedKeys(post);
       ok(body.keys.collections[extensionId], `keys object should have a key for ${extensionId}`);
+
+      // Try adding another key to make sure that the first post was
+      // OK, even on a new profile.
+      yield cryptoCollection._clear();
+      server.clearPosts();
+      // Restore the first posted keyring
+      server.addRecordInPast("storage-sync-crypto", post.body.data);
+      const extensionId2 = uuid();
+      newKeys = yield ExtensionStorageSync.ensureKeysFor([extensionId2]);
+      ok(newKeys.hasKeysFor([extensionId]), `didn't forget key for ${extensionId}`);
+      ok(newKeys.hasKeysFor([extensionId2]), `new key generated for ${extensionId2}`);
+
+      posts = server.getPosts();
+      // FIXME: some kind of bug where we try to repush the
+      // server_wins version multiple times in a single sync. We
+      // actually push 5 times as of this writing.
+      // See bug 1321571.
+      // equal(posts.length, 1);
+      const newPost = posts[posts.length - 1];
+      const newBody = yield assertPostedEncryptedKeys(newPost);
+      ok(newBody.keys.collections[extensionId], `keys object should have a key for ${extensionId}`);
+      ok(newBody.keys.collections[extensionId2], `keys object should have a key for ${extensionId2}`);
+
     });
   });
 });
 
 add_task(function* ensureKeysFor_pulls_key() {
   // ensureKeysFor is implemented by adding a key to our local record
   // and doing a sync. This means that if the same key exists
   // remotely, we get a "conflict". Ensure that we handle this
@@ -663,16 +714,17 @@ add_task(function* checkSyncKeyRing_over
               "keyring upload should be authorized");
         equal(postedKeys.headers["If-None-Match"], "*",
               "keyring upload should be to empty Kinto server");
         equal(postedKeys.path, collectionRecordsPath("storage-sync-crypto") + "/keys",
               "keyring upload should be to keyring path");
 
         let body = yield new KeyRingEncryptionRemoteTransformer().decode(postedKeys.body.data);
         ok(body.uuid, "new keyring should have a UUID");
+        equal(typeof body.uuid, "string", "keyring UUIDs should be strings");
         notEqual(body.uuid, "abcd",
                  "new keyring should not have the same UUID as previous keyring");
         ok(body.keys,
            "new keyring should have a keys attribute");
         ok(body.keys.default, "new keyring should have a default key");
         // We should keep the extension key that was in our uploaded version.
         deepEqual(extensionKey, body.keys.collections[extensionId],
                   "ensureKeysFor should have returned keyring with the same key that was uploaded");