Verifique nesta ordem
- O acesso às notificações está ativado para o Notification Tracker nas Configurações do Android.
- A Atividade em segundo plano está permitida, para que o celular não pare o app.
- O app não está em Configurações > Lista negra.
- O Registro do histórico não está em Não registrar.
- O outro app realmente mostra notificações (confira as configurações de notificação dele).
- Reinicie o celular. Algumas atualizações redefinem o acesso às notificações.
Ainda não funciona?
Envie um relatório de bug em Configurações > Sobre. Informe o modelo do celular e a versão do Android.