One thing I’d check is whether the issue is actually the permission set or the app object’s visibility configuration.
Since giving View All on Contacts works, it sounds like the permission set is being applied correctly. That narrows the problem to the app object itself rather than user permissions in general.
A few things I’d verify:
Is the app object enabled for that specific user or team?
Does the app object have its own object-level permissions that need to be granted in addition to the permission set?
Is the user assigned the correct app access/license if this object comes from a private app or marketplace app?
If you’re testing with an existing record, is there any record-level ownership or filtering preventing it from appearing?
If you can share:
whether this is a custom object or an app-created object,
how the object was created (private app, public app, or custom object),
and a screenshot of the permission configuration,
it’ll be much easier to narrow down where the access is breaking