結論
手元に複数の Android 端末があれば別の端末を試してみましょう。
SERVICE_NOT_AVAILABLE の本来の意味
there was a temporary error registering your device with Google. Try again in a few minutes. The app will reregister every time you launch it.
噂によると特定の端末で問題があるかも
https://groups.google.com/forum/#!topic/android-group-japan/3FNhh4FIFqU
