This can happen for honestly many different reasons and its not always easy to see exactly which one it is, so I try to narrow it down to a single person having the issue and work on them.
1. Like anything it can take a while for an app to show up, heck even my updates to my Canvas Apps that I use for Christmas inventory I wrote lol can take a couple of hours and its ANNOYING when you are trying to decorate and cannot find things.
2. I do not know if these are iOS or Android phones but that can also be an issue depending on the version of their phone, which can impact the version of the M365 app and Teams, oh and like for me, I always forget to have my wife update the Power Apps app, and so she does not work but mine does, so make sure they are using the correct versions AND giving it time AND have the proper license and proper security roles, groups etc.
3. As always validate your licenses and security for the apps, making sure the people are in the right security groups, assigned to the teams (or org level for M365 apps). This can be anything from DLP policies to missing people in a security group or copilot license is active or not assigned. Look at yours if it works, then compare yours to someone who does not work, or IF you are an admin don't. compare it to two people in the same organization (team preferably) and validate everything above.
Its hard without seeing your environment and having all these details, but also make sure that if an app has been shared, that its shared to everyone and not just a group, make sure that it does not require an admin to publish it or approve it for everyone in the M365 and Teams admins as well as the Tenant
If you are using Managed Environments, check there as well.
If these suggestions help resolve your issue, Please consider Marking the answer as such and also maybe a like.
Thank you!
Sincerely, Michael Gernaey