I was facing the same problem. I looked through a lot of SO posts and other forums and I found a solution that worked for me. FCM documentation says to use this method to get a token.
String refreshedToken = FirebaseInstanceId.getInstance().getToken();
I found a post online (I apologize, I don't remember which one. I found it a while ago) that used this method instead:
String refreshedToken = FirebaseInstanceId.getInstance().getToken() (String authorizedEntity, String scope);
FCM documentation describes the first method as:
Return the master token for the default Firebase project.
While the second one is described as:
Returns a token that authorizes an Entity to perform an action on behalf of the application identified by Instance ID.
This is similar to an OAuth2 token except, it applies to the application instance instead of a user.
For example, to get a token that can be used to send messages to an application via FirebaseMessaging, set to the sender ID, and set to "FCM".
I have been looking into why the first method call takes a longer time to return a token, but I haven't found an answer yet. Hope this helps.