Aunque intento otra respuesta sobre este problema, no se puede resolver. El ID del remitente es correcto, se agregan permisos, la clave API es verdadera.

Yo uso este post para crear el proyecto:http://developer.android.com/guide/google/gcm/gs.html#server-app

    GCMRegistrar.checkDevice(this);
    GCMRegistrar.checkManifest(this);
    String regId = GCMRegistrar.getRegistrationId(this);
    if (regId.equals("")) {
      GCMRegistrar.register(this, SENDER_ID);
      regId = GCMRegistrar.getRegistrationId(this);
    } else {
      Log.v(TAG, "Already registered");
    }
    String did = getDeviceID();

devuelve cadena vacía.