There could be multiple reasons,
Are you obfuscating? If yes, add proguard rules related to FCM classes
Check if you've added SHA-1 key in firebase console
Check mobile's Internet connection and date/time to be correct