Firebase for Android - W/PersistentConnection: pc_0 - Provided authentication credentials are invalid

Finally I found how to fix the problem thanks to the Firebase support engineers! :)

The trick is to wait for getting FirebaseAuth from FirebaseAuth.AuthStateListener (instead of getting it directly from the FirebaseAuth.getInstance()) prior to accessing Firebase Database at application startup: it looks like Firebase needs some time to initialize/renew user authentication.

So, the following code doesn't work correctly:

// Main Activity
protected void onCreate(...) {
   if (FirebaseAuth.getInstance().getCurrentUser() != null) {
      // accessing Firebase Database
   }
}

It must be like the this:

protected void onCreate(...) {
    //...
    authStateListener = new FirebaseAuth.AuthStateListener() {
        @Override
        public void onAuthStateChanged(@NonNull FirebaseAuth firebaseAuth) {
            FirebaseUser user = firebaseAuth.getCurrentUser();
            if (user != null) {
               // accessing Firebase Database
            }
        }
    };
    FirebaseAuth.getInstance().addAuthStateListener(authStateListener);
}

Alexander's answer did not work for me..

Seems that clearing all Google Play services storage solves the problem Settings => Apps => Google Play services => Storage => MANAGE STORAGE => CLEAR ALL DATA, this issue probably needs to be fixed by Firebase or Google.