--- a/dom/base/domerr.msg
+++ b/dom/base/domerr.msg
@@ -140,16 +140,17 @@ DOM4_MSG_DEF(QuotaExceededError, "The cu
 
 /* Push API errors. */
 DOM4_MSG_DEF(InvalidStateError, "Invalid service worker registration.", NS_ERROR_DOM_PUSH_INVALID_REGISTRATION_ERR)
 DOM4_MSG_DEF(NotAllowedError, "User denied permission to use the Push API.", NS_ERROR_DOM_PUSH_DENIED_ERR)
 DOM4_MSG_DEF(AbortError, "Error retrieving push subscription.", NS_ERROR_DOM_PUSH_ABORT_ERR)
 DOM4_MSG_DEF(NetworkError, "Push service unreachable.", NS_ERROR_DOM_PUSH_SERVICE_UNREACHABLE)
 DOM4_MSG_DEF(InvalidAccessError, "Invalid raw ECDSA P-256 public key.", NS_ERROR_DOM_PUSH_INVALID_KEY_ERR)
 DOM4_MSG_DEF(InvalidStateError, "A subscription with a different application server key already exists.", NS_ERROR_DOM_PUSH_MISMATCHED_KEY_ERR)
+DOM4_MSG_DEF(InvalidStateError, "GCM service disabled.", NS_ERROR_DOM_PUSH_GCM_DISABLED)
 
 /* Media errors */
 DOM4_MSG_DEF(AbortError,        "The fetching process for the media resource was aborted by the user agent at the user's request.", NS_ERROR_DOM_MEDIA_ABORT_ERR)
 DOM4_MSG_DEF(NotAllowedError,   "The play method is not allowed by the user agent or the platform in the current context, possibly because the user denied permission.", NS_ERROR_DOM_MEDIA_NOT_ALLOWED_ERR)
 DOM4_MSG_DEF(NotSupportedError, "The media resource indicated by the src attribute or assigned media provider object was not suitable.", NS_ERROR_DOM_MEDIA_NOT_SUPPORTED_ERR)
 
 DOM4_MSG_DEF(SyntaxError, "The URI is malformed.", NS_ERROR_DOM_MALFORMED_URI)
 DOM4_MSG_DEF(SyntaxError, "Invalid header name.", NS_ERROR_DOM_INVALID_HEADER_NAME)

--- a/mobile/android/base/java/org/mozilla/gecko/push/PushService.java
+++ b/mobile/android/base/java/org/mozilla/gecko/push/PushService.java
@@ -56,16 +56,22 @@ import java.util.Map;
  */
 @ReflectionTarget
 public class PushService implements BundleEventListener {
     private static final String LOG_TAG = "GeckoPushService";
 
     public static final String SERVICE_WEBPUSH = "webpush";
     public static final String SERVICE_FXA = "fxa";
 
+    public static final double ERROR_GCM_DISABLED = 2154627078L; // = NS_ERROR_DOM_PUSH_GCM_DISABLED
+
+    public static final String REPLY_BUNDLE_KEY_ERROR = "error";
+    public static final String ERROR_BUNDLE_KEY_MESSAGE = "message";
+    public static final String ERROR_BUNDLE_KEY_RESULT = "result";
+
     private static PushService sInstance;
 
     private static final String[] GECKO_EVENTS = new String[] {
             "PushServiceAndroidGCM:Configure",
             "PushServiceAndroidGCM:DumpRegistration",
             "PushServiceAndroidGCM:DumpSubscriptions",
             "PushServiceAndroidGCM:Initialized",
             "PushServiceAndroidGCM:Uninitialized",
@@ -165,17 +171,17 @@ public class PushService implements Bund
 
             // This decision will be re-addressed as part of Bug 1346061.
             if (!State.StateLabel.Married.equals(fxAccountState.getStateLabel())) {
                 Log.i(LOG_TAG, "FxA account not in Married state, not proceeding with registration renewal");
                 return;
             }
 
             // We'll obtain a new subscription as part of device registration.
-            if (FxAccountDeviceRegistrator.needToRenewRegistration(fxAccount.getDeviceRegistrationTimestamp())) {
+            if (FxAccountDeviceRegistrator.shouldRenewRegistration(fxAccount)) {
                 Log.i(LOG_TAG, "FxA device needs registration renewal");
                 FxAccountDeviceRegistrator.renewRegistration(context);
             }
         } catch (Exception e) {
             Log.e(LOG_TAG, "Got exception during startup; ignoring.", e);
             return;
         }
     }
@@ -462,17 +468,23 @@ public class PushService implements Bund
                 callback.sendSuccess(millis);
                 return;
             }
         } catch (GcmTokenClient.NeedsGooglePlayServicesException e) {
             // TODO: improve this.  Can we find a point where the user is *definitely* interacting
             // with the WebPush?  Perhaps we can show a dialog when interacting with the Push
             // permissions, and then be more aggressive showing this notification when we have
             // registrations and subscriptions that can't be advanced.
-            callback.sendError("To handle event [" + event + "], user interaction is needed to enable Google Play Services.");
+            String msg = "To handle event [" + event + "], user interaction is needed to enable Google Play Services.";
+            GeckoBundle reply = new GeckoBundle();
+            GeckoBundle error = new GeckoBundle();
+            error.putString(ERROR_BUNDLE_KEY_MESSAGE, msg);
+            error.putDouble(ERROR_BUNDLE_KEY_RESULT, ERROR_GCM_DISABLED);
+            reply.putBundle(REPLY_BUNDLE_KEY_ERROR, error);
+            callback.sendError(reply);
         }
     }
 
     private void processComponentState(@NonNull GeckoComponent component, boolean isReady) {
         if (component == GeckoComponent.FxAccountsPush) {
             isReadyFxAccountsPush = isReady;
 
         } else if (component == GeckoComponent.PushServiceAndroidGCM) {

--- a/mobile/android/components/FxAccountsPush.js
+++ b/mobile/android/components/FxAccountsPush.js
@@ -1,16 +1,14 @@
 /* jshint moz: true, esnext: true */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
-const Cc = Components.classes;
-const Ci = Components.interfaces;
-const Cu = Components.utils;
+const { classes: Cc, interfaces: Ci, utils: Cu } = Components;
 
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/Messaging.jsm");
 const {
   PushCrypto,
   getCryptoParams,
 } = Cu.import("resource://gre/modules/PushCrypto.jsm", {});
@@ -55,32 +53,38 @@ FxAccountsPush.prototype = {
       PushService.subscribe(FXA_PUSH_SCOPE,
         Services.scriptSecurityManager.getSystemPrincipal(),
         (result, subscription) => {
           if (Components.isSuccessCode(result)) {
             Log.d("FxAccountsPush got subscription");
             resolve(subscription);
           } else {
             Log.w("FxAccountsPush failed to subscribe", result);
-            reject(new Error("FxAccountsPush failed to subscribe"));
+            const err = new Error("FxAccountsPush failed to subscribe");
+            err.result = result;
+            reject(err);
           }
         });
     })
     .then(subscription => {
       EventDispatcher.instance.sendRequest({
         type: "FxAccountsPush:Subscribe:Response",
         subscription: {
           pushCallback: subscription.endpoint,
           pushPublicKey: urlsafeBase64Encode(subscription.getKey('p256dh')),
           pushAuthKey: urlsafeBase64Encode(subscription.getKey('auth'))
         }
       });
     })
     .catch(err => {
       Log.i("Error when registering FxA push endpoint " + err);
+      EventDispatcher.instance.sendRequest({
+        type: "FxAccountsPush:Subscribe:Response",
+        error: err.result.toString() // Convert to string because the GeckoBundle can't getLong();
+      });
     });
   },
 
   _unsubscribe() {
     Log.i("FxAccountsPush _unsubscribe");
     return new Promise((resolve) => {
       PushService.unsubscribe(FXA_PUSH_SCOPE,
         Services.scriptSecurityManager.getSystemPrincipal(),

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/FxAccountDevice.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/FxAccountDevice.java
@@ -30,26 +30,16 @@ public class FxAccountDevice {
     this.id = id;
     this.type = type;
     this.isCurrentDevice = isCurrentDevice;
     this.pushCallback = pushCallback;
     this.pushPublicKey = pushPublicKey;
     this.pushAuthKey = pushAuthKey;
   }
 
-  public static FxAccountDevice forRegister(String name, String type, String pushCallback,
-                                            String pushPublicKey, String pushAuthKey) {
-    return new FxAccountDevice(name, null, type, null, pushCallback, pushPublicKey, pushAuthKey);
-  }
-
-  public static FxAccountDevice forUpdate(String id, String name, String pushCallback,
-                                          String pushPublicKey, String pushAuthKey) {
-    return new FxAccountDevice(name, id, null, null, pushCallback, pushPublicKey, pushAuthKey);
-  }
-
   public static FxAccountDevice fromJson(ExtendedJSONObject json) {
     String name = json.getString(JSON_KEY_NAME);
     String id = json.getString(JSON_KEY_ID);
     String type = json.getString(JSON_KEY_TYPE);
     Boolean isCurrentDevice = json.getBoolean(JSON_KEY_ISCURRENTDEVICE);
     String pushCallback = json.getString(JSON_KEY_PUSH_CALLBACK);
     String pushPublicKey = json.getString(JSON_KEY_PUSH_PUBLICKEY);
     String pushAuthKey = json.getString(JSON_KEY_PUSH_AUTHKEY);
@@ -73,9 +63,52 @@ public class FxAccountDevice {
     if (this.pushPublicKey != null) {
       body.put(JSON_KEY_PUSH_PUBLICKEY, this.pushPublicKey);
     }
     if (this.pushAuthKey != null) {
       body.put(JSON_KEY_PUSH_AUTHKEY, this.pushAuthKey);
     }
     return body;
   }
+
+  public static class Builder {
+    private String id;
+    private String name;
+    private String type;
+    private Boolean isCurrentDevice;
+    private String pushCallback;
+    private String pushPublicKey;
+    private String pushAuthKey;
+
+    public void id(String id) {
+      this.id = id;
+    }
+
+    public void name(String name) {
+      this.name = name;
+    }
+
+    public void type(String type) {
+      this.type = type;
+    }
+
+    public void isCurrentDevice() {
+      this.isCurrentDevice = Boolean.TRUE;
+    }
+
+    public void pushCallback(String pushCallback) {
+      this.pushCallback = pushCallback;
+    }
+
+    public void pushPublicKey(String pushPublicKey) {
+      this.pushPublicKey = pushPublicKey;
+    }
+
+    public void pushAuthKey(String pushAuthKey) {
+      this.pushAuthKey = pushAuthKey;
+    }
+
+    public FxAccountDevice build() {
+      return new FxAccountDevice(this.name, this.id, this.type, this.isCurrentDevice,
+                                 this.pushCallback, this.pushPublicKey, this.pushAuthKey);
+    }
+  }
 }

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/FxAccountDeviceRegistrator.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/FxAccountDeviceRegistrator.java
@@ -1,17 +1,19 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 package org.mozilla.gecko.fxa;
 
 import android.content.Context;
 import android.content.Intent;
+import android.support.annotation.NonNull;
 import android.support.annotation.Nullable;
+import android.support.annotation.VisibleForTesting;
 import android.text.TextUtils;
 import android.util.Log;
 
 import org.mozilla.gecko.background.common.log.Logger;
 import org.mozilla.gecko.background.fxa.FxAccountClient;
 import org.mozilla.gecko.background.fxa.FxAccountClient20;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.AccountStatusResponse;
 import org.mozilla.gecko.background.fxa.FxAccountClient20.RequestDelegate;
@@ -29,67 +31,89 @@ import java.lang.ref.WeakReference;
 import java.lang.reflect.InvocationTargetException;
 import java.lang.reflect.Method;
 import java.security.GeneralSecurityException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 
 /* This class provides a way to register the current device against FxA
  * and also stores the registration details in the Android FxAccount.
- * This should be used in a state where we possess a sessionToken, most likely the Married state.
+ * This should be used in a state where we possess a sessionToken, most likely the Engaged/Married states.
  */
 public class FxAccountDeviceRegistrator implements BundleEventListener {
   private static final String LOG_TAG = "FxADeviceRegistrator";
 
   // The autopush endpoint expires stale channel subscriptions every 30 days (at a set time during
   // the month, although we don't depend on this). To avoid the FxA service channel silently
   // expiring from underneath us, we unsubscribe and resubscribe every 21 days.
   // Note that this simple schedule means that we might unsubscribe perfectly valid (but old)
   // subscriptions. This will be improved as part of Bug 1345651.
-  private static final long TIME_BETWEEN_CHANNEL_REGISTRATION_IN_MILLIS = 21 * 24 * 60 * 60 * 1000L;
+  @VisibleForTesting
+  static final long TIME_BETWEEN_CHANNEL_REGISTRATION_IN_MILLIS = 21 * 24 * 60 * 60 * 1000L;
+
+  @VisibleForTesting
+  static final long RETRY_TIME_AFTER_GCM_DISABLED_ERROR = 15 * 24 * 60 * 60 * 1000L;
+
+
+  public static final String PUSH_SUBSCRIPTION_REPLY_BUNDLE_KEY_ERROR = "error";
+  @VisibleForTesting
+  static final long ERROR_GCM_DISABLED = 2154627078L; // = NS_ERROR_DOM_PUSH_GCM_DISABLED
 
   // The current version of the device registration, we use this to re-register
   // devices after we update what we send on device registration.
-  public static final Integer DEVICE_REGISTRATION_VERSION = 2;
+  @VisibleForTesting
+  static final Integer DEVICE_REGISTRATION_VERSION = 2;
 
   private static FxAccountDeviceRegistrator instance;
   private final WeakReference<Context> context;
 
   private FxAccountDeviceRegistrator(Context appContext) {
-    this.context = new WeakReference<Context>(appContext);
+    this.context = new WeakReference<>(appContext);
   }
 
   private static FxAccountDeviceRegistrator getInstance(Context appContext) throws ClassNotFoundException, NoSuchMethodException, InvocationTargetException, IllegalAccessException {
     if (instance == null) {
-      FxAccountDeviceRegistrator tempInstance = new FxAccountDeviceRegistrator(appContext);
+      final FxAccountDeviceRegistrator tempInstance = new FxAccountDeviceRegistrator(appContext);
       tempInstance.setupListeners(); // Set up listener for FxAccountPush:Subscribe:Response
       instance = tempInstance;
     }
     return instance;
   }
 
-  public static boolean needToRenewRegistration(final long timestamp) {
+  public static boolean shouldRegister(final AndroidFxAccount fxAccount) {
+    if (fxAccount.getDeviceRegistrationVersion() != FxAccountDeviceRegistrator.DEVICE_REGISTRATION_VERSION ||
+            TextUtils.isEmpty(fxAccount.getDeviceId())) {
+      return true;
+    }
+    // At this point, we have a working up-to-date registration, but it might be a partial one
+    // (no push registration).
+    return fxAccount.getDevicePushRegistrationError() == ERROR_GCM_DISABLED &&
+           (System.currentTimeMillis() - fxAccount.getDevicePushRegistrationErrorTime()) > RETRY_TIME_AFTER_GCM_DISABLED_ERROR;
+  }
+
+  public static boolean shouldRenewRegistration(final AndroidFxAccount fxAccount) {
+    final long deviceRegistrationTimestamp = fxAccount.getDeviceRegistrationTimestamp();
     // NB: we're comparing wall clock to wall clock, at different points in time.
     // It's possible that wall clocks have changed, and our comparison will be meaningless.
     // However, this happens in the context of a sync, and we won't be able to sync anyways if our
     // wall clock deviates too much from time on the server.
-    return (System.currentTimeMillis() - timestamp) > TIME_BETWEEN_CHANNEL_REGISTRATION_IN_MILLIS;
+    return (System.currentTimeMillis() - deviceRegistrationTimestamp) > TIME_BETWEEN_CHANNEL_REGISTRATION_IN_MILLIS;
   }
 
   public static void register(Context context) {
-    Context appContext = context.getApplicationContext();
+    final Context appContext = context.getApplicationContext();
     try {
       getInstance(appContext).beginRegistration(appContext);
     } catch (Exception e) {
       Log.e(LOG_TAG, "Could not start FxA device registration", e);
     }
   }
 
   public static void renewRegistration(Context context) {
-    Context appContext = context.getApplicationContext();
+    final Context appContext = context.getApplicationContext();
     try {
       getInstance(appContext).beginRegistrationRenewal(appContext);
     } catch (Exception e) {
       Log.e(LOG_TAG, "Could not start FxA device re-registration", e);
     }
   }
 
   private void beginRegistration(Context context) {
@@ -117,60 +141,76 @@ public class FxAccountDeviceRegistrator 
     final AndroidFxAccount fxAccount = AndroidFxAccount.fromContext(context);
     intent.putExtra("org.mozilla.gecko.intent.PROFILE_NAME", fxAccount.getProfile());
     return intent;
   }
 
   @Override
   public void handleMessage(String event, GeckoBundle message, EventCallback callback) {
     if ("FxAccountsPush:Subscribe:Response".equals(event)) {
-      doFxaRegistration(message.getBundle("subscription"));
+      handlePushSubscriptionResponse(message);
     } else {
       Log.e(LOG_TAG, "No action defined for " + event);
     }
   }
 
-  private void doFxaRegistration(GeckoBundle subscription) {
+  private void handlePushSubscriptionResponse(final GeckoBundle message) {
+    // Make sure the context has not been gc'd during the push registration
+    // and the FxAccount still exists.
     final Context context = this.context.get();
-    if (this.context == null) {
+    if (context == null) {
       throw new IllegalStateException("Application context has been gc'ed");
     }
-    doFxaRegistration(context, subscription, true);
-  }
-
-  private static void doFxaRegistration(final Context context, final GeckoBundle subscription, final boolean allowRecursion) {
-    String pushCallback = subscription.getString("pushCallback");
-    String pushPublicKey = subscription.getString("pushPublicKey");
-    String pushAuthKey = subscription.getString("pushAuthKey");
-
     final AndroidFxAccount fxAccount = AndroidFxAccount.fromContext(context);
     if (fxAccount == null) {
       Log.e(LOG_TAG, "AndroidFxAccount is null");
       return;
     }
+
+    fxAccount.resetDevicePushRegistrationError();
+    final long error = getSubscriptionReplyError(message);
+
+    final FxAccountDevice device;
+    if (error == 0L) {
+      Log.i(LOG_TAG, "Push registration succeeded. Beginning normal FxA Registration.");
+      device = buildFxAccountDevice(context, fxAccount, message.getBundle("subscription"));
+    } else {
+      fxAccount.setDevicePushRegistrationError(error, System.currentTimeMillis());
+      Log.i(LOG_TAG, "Push registration failed. Beginning degraded FxA Registration.");
+      device = buildFxAccountDevice(context, fxAccount);
+    }
+
+    doFxaRegistration(context, fxAccount, device, true);
+  }
+
+  private long getSubscriptionReplyError(final GeckoBundle message) {
+    String errorStr = message.getString(PUSH_SUBSCRIPTION_REPLY_BUNDLE_KEY_ERROR);
+    if (TextUtils.isEmpty(errorStr)) {
+      return 0L;
+    }
+    return Long.parseLong(errorStr);
+  }
+
+  private static void doFxaRegistration(final Context context, final AndroidFxAccount fxAccount,
+                                        final FxAccountDevice device, final boolean allowRecursion) {
     final byte[] sessionToken;
     try {
       sessionToken = fxAccount.getState().getSessionToken();
     } catch (State.NotASessionTokenState e) {
       Log.e(LOG_TAG, "Could not get a session token", e);
       return;
     }
-    final FxAccountDevice device;
-    String deviceId = fxAccount.getDeviceId();
-    String clientName = getClientName(fxAccount, context);
-    if (TextUtils.isEmpty(deviceId)) {
+
+    if (device.id == null) {
       Log.i(LOG_TAG, "Attempting registration for a new device");
-      device = FxAccountDevice.forRegister(clientName, "mobile", pushCallback, pushPublicKey, pushAuthKey);
     } else {
       Log.i(LOG_TAG, "Attempting registration for an existing device");
-      Logger.pii(LOG_TAG, "Device ID: " + deviceId);
-      device = FxAccountDevice.forUpdate(deviceId, clientName, pushCallback, pushPublicKey, pushAuthKey);
     }
 
-    ExecutorService executor = Executors.newSingleThreadExecutor(); // Not called often, it's okay to spawn another thread
+    final ExecutorService executor = Executors.newSingleThreadExecutor(); // Not called often, it's okay to spawn another thread
     final FxAccountClient20 fxAccountClient =
             new FxAccountClient20(fxAccount.getAccountServerURI(), executor);
     fxAccountClient.registerOrUpdateDevice(sessionToken, device, new RequestDelegate<FxAccountDevice>() {
       @Override
       public void handleError(Exception e) {
         Log.e(LOG_TAG, "Error while updating a device registration: ", e);
         fxAccount.setDeviceRegistrationTimestamp(0L);
       }
@@ -180,48 +220,83 @@ public class FxAccountDeviceRegistrator 
         Log.e(LOG_TAG, "Error while updating a device registration: ", error);
 
         fxAccount.setDeviceRegistrationTimestamp(0L);
 
         if (error.httpStatusCode == 400) {
           if (error.apiErrorNumber == FxAccountRemoteError.UNKNOWN_DEVICE) {
             recoverFromUnknownDevice(fxAccount);
           } else if (error.apiErrorNumber == FxAccountRemoteError.DEVICE_SESSION_CONFLICT) {
-            recoverFromDeviceSessionConflict(error, fxAccountClient, sessionToken, fxAccount, context,
-                    subscription, allowRecursion);
+            // This can happen if a device was already registered using our session token, and we
+            // tried to create a new one (no id field).
+            recoverFromDeviceSessionConflict(error, fxAccountClient, sessionToken, fxAccount, device,
+                    context, allowRecursion);
           }
         } else
         if (error.httpStatusCode == 401
                 && error.apiErrorNumber == FxAccountRemoteError.INVALID_AUTHENTICATION_TOKEN) {
           handleTokenError(error, fxAccountClient, fxAccount);
         } else {
           logErrorAndResetDeviceRegistrationVersionAndTimestamp(error, fxAccount);
         }
       }
 
       @Override
       public void handleSuccess(FxAccountDevice result) {
         Log.i(LOG_TAG, "Device registration complete");
         Logger.pii(LOG_TAG, "Registered device ID: " + result.id);
+        Log.i(LOG_TAG, "Setting DEVICE_REGISTRATION_VERSION to " + DEVICE_REGISTRATION_VERSION);
         fxAccount.setFxAUserData(result.id, DEVICE_REGISTRATION_VERSION, System.currentTimeMillis());
       }
     });
   }
 
+  private static FxAccountDevice buildFxAccountDevice(Context context, AndroidFxAccount fxAccount) {
+    return makeFxADeviceCommonBuilder(context, fxAccount).build();
+  }
+
+  private static FxAccountDevice buildFxAccountDevice(Context context, AndroidFxAccount fxAccount, @NonNull GeckoBundle subscription) {
+    final FxAccountDevice.Builder builder = makeFxADeviceCommonBuilder(context, fxAccount);
+    final String pushCallback = subscription.getString("pushCallback");
+    final String pushPublicKey = subscription.getString("pushPublicKey");
+    final String pushAuthKey = subscription.getString("pushAuthKey");
+    if (!TextUtils.isEmpty(pushCallback) && !TextUtils.isEmpty(pushPublicKey) &&
+        !TextUtils.isEmpty(pushAuthKey)) {
+      builder.pushCallback(pushCallback);
+      builder.pushPublicKey(pushPublicKey);
+      builder.pushAuthKey(pushAuthKey);
+    }
+    return builder.build();
+  }
+
+  // Do not call this directly, use buildFxAccountDevice instead.
+  private static FxAccountDevice.Builder makeFxADeviceCommonBuilder(Context context, AndroidFxAccount fxAccount) {
+    final String deviceId = fxAccount.getDeviceId();
+    final String clientName = getClientName(fxAccount, context);
+
+    final FxAccountDevice.Builder builder = new FxAccountDevice.Builder();
+    builder.name(clientName);
+    builder.type("mobile");
+    if (!TextUtils.isEmpty(deviceId)) {
+      builder.id(deviceId);
+    }
+    return builder;
+  }
+
   private static void logErrorAndResetDeviceRegistrationVersionAndTimestamp(
       final FxAccountClientRemoteException error, final AndroidFxAccount fxAccount) {
     Log.e(LOG_TAG, "Device registration failed", error);
     fxAccount.resetDeviceRegistrationVersion();
     fxAccount.setDeviceRegistrationTimestamp(0L);
   }
 
   @Nullable
   private static String getClientName(final AndroidFxAccount fxAccount, final Context context) {
     try {
-      SharedPreferencesClientsDataDelegate clientsDataDelegate =
+      final SharedPreferencesClientsDataDelegate clientsDataDelegate =
           new SharedPreferencesClientsDataDelegate(fxAccount.getSyncPrefs(), context);
       return clientsDataDelegate.getClientName();
     } catch (UnsupportedEncodingException | GeneralSecurityException e) {
       Log.e(LOG_TAG, "Unable to get client name.", e);
       return null;
     }
   }
 
@@ -237,17 +312,17 @@ public class FxAccountDeviceRegistrator 
       }
 
       @Override
       public void handleFailure(FxAccountClientRemoteException e) {
       }
 
       @Override
       public void handleSuccess(AccountStatusResponse result) {
-        State doghouseState = fxAccount.getState().makeDoghouseState();
+        final State doghouseState = fxAccount.getState().makeDoghouseState();
         if (!result.exists) {
           Log.i(LOG_TAG, "token invalidated because the account no longer exists");
           // TODO: Should be in a "I have an Android account, but the FxA is gone." State.
           // This will do for now..
           fxAccount.setState(doghouseState);
           return;
         }
         Log.e(LOG_TAG, "sessionToken invalid");
@@ -263,19 +338,22 @@ public class FxAccountDeviceRegistrator 
 
   /**
    * Will call delegate#complete in all cases
    */
   private static void recoverFromDeviceSessionConflict(final FxAccountClientRemoteException error,
                                                        final FxAccountClient fxAccountClient,
                                                        final byte[] sessionToken,
                                                        final AndroidFxAccount fxAccount,
+                                                       final FxAccountDevice device,
                                                        final Context context,
-                                                       final GeckoBundle subscription,
                                                        final boolean allowRecursion) {
+    // Recovery strategy: re-try a registration, UPDATING (instead of creating) the device.
+    // We do that by finding the device ID who conflicted with us and try a registration update
+    // using that id.
     Log.w(LOG_TAG, "device session conflict, attempting to ascertain the correct device id");
     fxAccountClient.deviceList(sessionToken, new RequestDelegate<FxAccountDevice[]>() {
       private void onError() {
         Log.e(LOG_TAG, "failed to recover from device-session conflict");
         logErrorAndResetDeviceRegistrationVersionAndTimestamp(error, fxAccount);
       }
 
       @Override
@@ -285,35 +363,39 @@ public class FxAccountDeviceRegistrator 
 
       @Override
       public void handleFailure(FxAccountClientRemoteException e) {
         onError();
       }
 
       @Override
       public void handleSuccess(FxAccountDevice[] devices) {
-        for (FxAccountDevice device : devices) {
-          if (device.isCurrentDevice) {
-            fxAccount.setFxAUserData(device.id, 0, 0L); // Reset device registration version/timestamp
-            if (!allowRecursion) {
-              Log.d(LOG_TAG, "Failure to register a device on the second try");
-              break;
-            }
-            doFxaRegistration(context, subscription, false);
-            return;
+        for (final FxAccountDevice fxaDevice : devices) {
+          if (!fxaDevice.isCurrentDevice) {
+            continue;
           }
+          fxAccount.setFxAUserData(fxaDevice.id, 0, 0L); // Reset device registration version/timestamp
+          if (!allowRecursion) {
+            Log.d(LOG_TAG, "Failure to register a device on the second try");
+            break;
+          }
+          final FxAccountDevice updatedDevice = new FxAccountDevice(device.name, fxaDevice.id, device.type,
+                                                                    device.isCurrentDevice, device.pushCallback,
+                                                                    device.pushPublicKey, device.pushAuthKey);
+          doFxaRegistration(context, fxAccount, updatedDevice, false);
+          return;
         }
         onError();
       }
     });
   }
 
   private void setupListeners() throws ClassNotFoundException, NoSuchMethodException,
           InvocationTargetException, IllegalAccessException {
     // We have no choice but to use reflection here, sorry :(
-    Class<?> eventDispatcher = Class.forName("org.mozilla.gecko.EventDispatcher");
-    Method getInstance = eventDispatcher.getMethod("getInstance");
-    Object instance = getInstance.invoke(null);
-    Method registerBackgroundThreadListener = eventDispatcher.getMethod("registerBackgroundThreadListener",
+    final Class<?> eventDispatcher = Class.forName("org.mozilla.gecko.EventDispatcher");
+    final Method getInstance = eventDispatcher.getMethod("getInstance");
+    final Object instance = getInstance.invoke(null);
+    final Method registerBackgroundThreadListener = eventDispatcher.getMethod("registerBackgroundThreadListener",
             BundleEventListener.class, String[].class);
     registerBackgroundThreadListener.invoke(instance, this, new String[] { "FxAccountsPush:Subscribe:Response" });
   }
 }

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/authenticator/AndroidFxAccount.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/authenticator/AndroidFxAccount.java
@@ -10,17 +10,16 @@ import android.annotation.SuppressLint;
 import android.app.Activity;
 import android.content.ContentResolver;
 import android.content.Context;
 import android.content.Intent;
 import android.content.SharedPreferences;
 import android.os.Bundle;
 import android.os.Handler;
 import android.os.ResultReceiver;
-import android.support.annotation.NonNull;
 import android.support.annotation.Nullable;
 import android.support.v4.content.LocalBroadcastManager;
 import android.text.TextUtils;
 import android.util.Log;
 
 import org.mozilla.gecko.background.common.GlobalConstants;
 import org.mozilla.gecko.background.common.log.Logger;
 import org.mozilla.gecko.background.fxa.FxAccountUtils;
@@ -34,16 +33,18 @@ import org.mozilla.gecko.fxa.sync.FxAcco
 import org.mozilla.gecko.sync.ExtendedJSONObject;
 import org.mozilla.gecko.sync.Utils;
 import org.mozilla.gecko.sync.setup.Constants;
 import org.mozilla.gecko.util.ThreadUtils;
 
 import java.io.UnsupportedEncodingException;
 import java.net.URISyntaxException;
 import java.security.GeneralSecurityException;
+import java.text.NumberFormat;
+import java.text.ParseException;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.Semaphore;
 
@@ -75,16 +76,18 @@ public class AndroidFxAccount {
   public static final String BUNDLE_KEY_BUNDLE_VERSION = "version";
   public static final String BUNDLE_KEY_STATE_LABEL = "stateLabel";
   public static final String BUNDLE_KEY_STATE = "state";
   public static final String BUNDLE_KEY_PROFILE_JSON = "profile";
 
   public static final String ACCOUNT_KEY_DEVICE_ID = "deviceId";
   public static final String ACCOUNT_KEY_DEVICE_REGISTRATION_VERSION = "deviceRegistrationVersion";
   private static final String ACCOUNT_KEY_DEVICE_REGISTRATION_TIMESTAMP = "deviceRegistrationTimestamp";
+  private static final String ACCOUNT_KEY_DEVICE_PUSH_REGISTRATION_ERROR = "devicePushRegistrationError";
+  private static final String ACCOUNT_KEY_DEVICE_PUSH_REGISTRATION_ERROR_TIME = "devicePushRegistrationErrorTime";
 
   // Account authentication token type for fetching account profile.
   public static final String PROFILE_OAUTH_TOKEN_TYPE = "oauth::profile";
 
   // Services may request OAuth tokens from the Firefox Account dynamically.
   // Each such token is prefixed with "oauth::" and a service-dependent scope.
   // Such tokens should be destroyed when the account is removed from the device.
   // This list collects all the known "oauth::" token types in order to delete them when necessary.
@@ -797,50 +800,49 @@ public class AndroidFxAccount {
         intent.putExtra(FxAccountProfileService.KEY_AUTH_TOKEN, authToken);
         intent.putExtra(FxAccountProfileService.KEY_PROFILE_SERVER_URI, getProfileServerURI());
         intent.putExtra(FxAccountProfileService.KEY_RESULT_RECEIVER, new ProfileResultReceiver(new Handler()));
         context.startService(intent);
       }
     });
   }
 
+  @SuppressWarnings("unchecked")
+  private <T extends Number> T getUserDataNumber(String key, T defaultValue) {
+    final String numStr = accountManager.getUserData(account, key);
+    if (TextUtils.isEmpty(numStr)) {
+      return defaultValue;
+    }
+    try {
+      return (T) NumberFormat.getInstance().parse(numStr);
+    } catch (ParseException e) {
+      Logger.warn(LOG_TAG, "Couldn't parse " + key + "; defaulting to 0L.", e);
+      return defaultValue;
+    }
+  }
+
   @Nullable
   public synchronized String getDeviceId() {
     return accountManager.getUserData(account, ACCOUNT_KEY_DEVICE_ID);
   }
 
-  @NonNull
   public synchronized int getDeviceRegistrationVersion() {
-    String versionStr = accountManager.getUserData(account, ACCOUNT_KEY_DEVICE_REGISTRATION_VERSION);
-    if (TextUtils.isEmpty(versionStr)) {
-      return 0;
-    } else {
-      try {
-        return Integer.parseInt(versionStr);
-      } catch (NumberFormatException ex) {
-        return 0;
-      }
-    }
+    return getUserDataNumber(ACCOUNT_KEY_DEVICE_REGISTRATION_VERSION, 0);
   }
 
   public synchronized long getDeviceRegistrationTimestamp() {
-    final String timestampStr = accountManager.getUserData(account, ACCOUNT_KEY_DEVICE_REGISTRATION_TIMESTAMP);
-
-    if (TextUtils.isEmpty(timestampStr)) {
-      return 0L;
-    }
+    return getUserDataNumber(ACCOUNT_KEY_DEVICE_REGISTRATION_TIMESTAMP, 0L);
+  }
 
-    // Long.parseLong might throw; while it's not expected that this might happen, let's not risk
-    // crashing here as this method will be called on startup.
-    try {
-      return Long.parseLong(timestampStr);
-    } catch (NumberFormatException e) {
-      Logger.warn(LOG_TAG, "Couldn't parse deviceRegistrationTimestamp; defaulting to 0L.", e);
-      return 0L;
-    }
+  public synchronized long getDevicePushRegistrationError() {
+    return getUserDataNumber(ACCOUNT_KEY_DEVICE_PUSH_REGISTRATION_ERROR, 0L);
+  }
+
+  public synchronized long getDevicePushRegistrationErrorTime() {
+    return getUserDataNumber(ACCOUNT_KEY_DEVICE_PUSH_REGISTRATION_ERROR_TIME, 0L);
   }
 
   public synchronized void setDeviceId(String id) {
     accountManager.setUserData(account, ACCOUNT_KEY_DEVICE_ID, id);
   }
 
   public synchronized void setDeviceRegistrationVersion(int deviceRegistrationVersion) {
     accountManager.setUserData(account, ACCOUNT_KEY_DEVICE_REGISTRATION_VERSION,
@@ -859,16 +861,25 @@ public class AndroidFxAccount {
   public synchronized void setFxAUserData(String id, int deviceRegistrationVersion, long timestamp) {
     accountManager.setUserData(account, ACCOUNT_KEY_DEVICE_ID, id);
     accountManager.setUserData(account, ACCOUNT_KEY_DEVICE_REGISTRATION_VERSION,
             Integer.toString(deviceRegistrationVersion));
     accountManager.setUserData(account, ACCOUNT_KEY_DEVICE_REGISTRATION_TIMESTAMP,
             Long.toString(timestamp));
   }
 
+  public synchronized void setDevicePushRegistrationError(long error, long errorTimeMs) {
+    accountManager.setUserData(account, ACCOUNT_KEY_DEVICE_PUSH_REGISTRATION_ERROR, Long.toString(error));
+    accountManager.setUserData(account, ACCOUNT_KEY_DEVICE_PUSH_REGISTRATION_ERROR_TIME, Long.toString(errorTimeMs));
+  }
+
+  public synchronized void resetDevicePushRegistrationError() {
+    setDevicePushRegistrationError(0L, 0l);
+  }
+
   @SuppressLint("ParcelCreator") // The CREATOR field is defined in the super class.
   private class ProfileResultReceiver extends ResultReceiver {
     public ProfileResultReceiver(Handler handler) {
       super(handler);
     }
 
     @Override
     protected void onReceiveResult(int resultCode, Bundle bundle) {

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/sync/FxAccountSyncAdapter.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/fxa/sync/FxAccountSyncAdapter.java
@@ -404,23 +404,22 @@ public class FxAccountSyncAdapter extend
     tokenServerclient.getTokenFromBrowserIDAssertion(assertion, true, clientState, delegate);
   }
 
   public void maybeRegisterDevice(Context context, AndroidFxAccount fxAccount) {
     // Register the device if necessary (asynchronous, in another thread).
     // As part of device registration, we obtain a PushSubscription, register our push endpoint
     // with FxA, and update account data with fxaDeviceId, which is part of our synced
     // clients record.
-    if (fxAccount.getDeviceRegistrationVersion() != FxAccountDeviceRegistrator.DEVICE_REGISTRATION_VERSION
-            || TextUtils.isEmpty(fxAccount.getDeviceId())) {
+    if (FxAccountDeviceRegistrator.shouldRegister(fxAccount)) {
       FxAccountDeviceRegistrator.register(context);
       // We might need to re-register periodically to ensure our FxA push subscription is valid.
       // This involves unsubscribing, subscribing and updating remote FxA device record with
       // new push subscription information.
-    } else if (FxAccountDeviceRegistrator.needToRenewRegistration(fxAccount.getDeviceRegistrationTimestamp())) {
+    } else if (FxAccountDeviceRegistrator.shouldRenewRegistration(fxAccount)) {
       FxAccountDeviceRegistrator.renewRegistration(context);
     }
   }
 
   /**
    * A trivial Sync implementation that does not cache client keys,
    * certificates, or tokens.
    *

new file mode 100644
--- /dev/null
+++ b/mobile/android/tests/background/junit4/src/org/mozilla/gecko/fxa/TestFxAccountDeviceRegistrator.java
@@ -0,0 +1,91 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+package org.mozilla.gecko.fxa;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.Mock;
+import org.mockito.MockitoAnnotations;
+import org.mozilla.gecko.background.testhelpers.TestRunner;
+import org.mozilla.gecko.fxa.authenticator.AndroidFxAccount;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.mockito.Mockito.when;
+
+@RunWith(TestRunner.class)
+public class TestFxAccountDeviceRegistrator {
+
+    @Mock
+    AndroidFxAccount fxAccount;
+
+    @Before
+    public void init() {
+        // Process Mockito annotations
+        MockitoAnnotations.initMocks(this);
+    }
+
+    @Test
+    public void shouldRegister() {
+        // Assuming there is no previous push registration errors recorded:
+        when(fxAccount.getDevicePushRegistrationError()).thenReturn(0L);
+        when(fxAccount.getDevicePushRegistrationErrorTime()).thenReturn(0L);
+
+        // Should return false if the device registration version is up-to-date and a device ID is stored.
+        // (general case after a successful device registration)
+        when(fxAccount.getDeviceRegistrationVersion()).thenReturn(FxAccountDeviceRegistrator.DEVICE_REGISTRATION_VERSION);
+        when(fxAccount.getDeviceId()).thenReturn("bogusdeviceid");
+        assertFalse(FxAccountDeviceRegistrator.shouldRegister(fxAccount));
+
+        // Should return true if the device registration version is up-to-date but no device ID is stored.
+        // (data mangling)
+        when(fxAccount.getDeviceRegistrationVersion()).thenReturn(FxAccountDeviceRegistrator.DEVICE_REGISTRATION_VERSION);
+        when(fxAccount.getDeviceId()).thenReturn(null);
+        assertTrue(FxAccountDeviceRegistrator.shouldRegister(fxAccount));
+
+        // Should return true if the device ID is stored but no device registration version can be found.
+        // (data mangling)
+        when(fxAccount.getDeviceRegistrationVersion()).thenReturn(0);
+        when(fxAccount.getDeviceId()).thenReturn("bogusid");
+        assertTrue(FxAccountDeviceRegistrator.shouldRegister(fxAccount));
+
+        // Should return true if the device registration version is too old.
+        // (code update pushed)
+        when(fxAccount.getDeviceRegistrationVersion()).thenReturn(FxAccountDeviceRegistrator.DEVICE_REGISTRATION_VERSION - 1);
+        assertTrue(FxAccountDeviceRegistrator.shouldRegister(fxAccount));
+
+        // Should return true if the device registration is OK, but we didn't get a push subscription because
+        // Google Play Services were unavailable at the time and the retry delay is passed.
+        when(fxAccount.getDeviceRegistrationVersion()).thenReturn(FxAccountDeviceRegistrator.DEVICE_REGISTRATION_VERSION);
+        when(fxAccount.getDevicePushRegistrationError()).thenReturn(FxAccountDeviceRegistrator.ERROR_GCM_DISABLED);
+        when(fxAccount.getDevicePushRegistrationErrorTime()).thenReturn(System.currentTimeMillis() -
+                                                                        FxAccountDeviceRegistrator.RETRY_TIME_AFTER_GCM_DISABLED_ERROR - 1);
+        assertTrue(FxAccountDeviceRegistrator.shouldRegister(fxAccount));
+
+        // Should return false if the device registration is OK, but we didn't get a push subscription because
+        // Google Play Services were unavailable at the time and the retry delay has not passed.
+        // We assume that RETRY_TIME_AFTER_GCM_DISABLED_ERROR is longer than the time it takes to execute this test :)
+        when(fxAccount.getDevicePushRegistrationErrorTime()).thenReturn(System.currentTimeMillis());
+        assertFalse(FxAccountDeviceRegistrator.shouldRegister(fxAccount));
+
+        // Should return false if the device registration is OK, but we didn't get a push subscription because
+        // an unknown error happened at the time.
+        when(fxAccount.getDevicePushRegistrationError()).thenReturn(12345L);
+        assertFalse(FxAccountDeviceRegistrator.shouldRegister(fxAccount));
+    }
+
+    @Test
+    public void shouldRenewRegistration() {
+        // Should return true if our last push registration was done a day before our expiration threshold.
+        when(fxAccount.getDeviceRegistrationTimestamp()).thenReturn(System.currentTimeMillis() -
+                                                                    FxAccountDeviceRegistrator.TIME_BETWEEN_CHANNEL_REGISTRATION_IN_MILLIS -
+                                                                    1 * 24 * 60 * 60 * 1000L);
+
+        // Should return false if our last push registration is recent enough.
+        // We assume that TIME_BETWEEN_CHANNEL_REGISTRATION_IN_MILLIS is longer than a day + the time it takes to run this test.
+        when(fxAccount.getDeviceRegistrationTimestamp()).thenReturn(System.currentTimeMillis() -
+                                                                    1 * 24 * 60 * 60 * 1000L);
+    }
+}

--- a/xpcom/base/ErrorList.py
+++ b/xpcom/base/ErrorList.py
@@ -1054,16 +1054,17 @@ with modules["DOM_ANIM"]:
 # =======================================================================
 with modules["DOM_PUSH"]:
     errors["NS_ERROR_DOM_PUSH_INVALID_REGISTRATION_ERR"] = FAILURE(1)
     errors["NS_ERROR_DOM_PUSH_DENIED_ERR"] = FAILURE(2)
     errors["NS_ERROR_DOM_PUSH_ABORT_ERR"] = FAILURE(3)
     errors["NS_ERROR_DOM_PUSH_SERVICE_UNREACHABLE"] = FAILURE(4)
     errors["NS_ERROR_DOM_PUSH_INVALID_KEY_ERR"] = FAILURE(5)
     errors["NS_ERROR_DOM_PUSH_MISMATCHED_KEY_ERR"] = FAILURE(6)
+    errors["NS_ERROR_DOM_PUSH_GCM_DISABLED"] = FAILURE(7)
 
 
 # =======================================================================
 # 41: NS_ERROR_MODULE_DOM_MEDIA
 # =======================================================================
 with modules["DOM_MEDIA"]:
     # HTMLMediaElement API errors from https://html.spec.whatwg.org/multipage/embedded-content.html#media-elements
     errors["NS_ERROR_DOM_MEDIA_ABORT_ERR"] = FAILURE(1)