A user needs full read/write permissions for all contacts; does the user in question have this? Often folks have full read/write permissions to contacts they own, which can cause some confusion.
Make sure the user in question has lists permissions as well. This permission is listed under the marketing tab in the user permissions screen, which means it's often missed.
There's currently a known issue with the contacts scope where certain app/portal combinations cannot be approved unless the user is a super admin. If you've checked the above and you're still experiencing issues, this might be the problem. The most immediate solution while this issue persists is to have a super admin approve the integration instead.
Feel free to reach back out with the Hub ID(s) and user names of the affected portals if you want me to investigate whether or not the portals are affected by the known issue I mentioned above.