Ok I think I understand what’s happening. On the object in question, are they the direct owner of that record? If you haven’t set up custom sharing rules for the custom object, users within the same role hierarchy won’t be able to edit eachother’s records.
When you’re enabling edit/view all, it allows users to modify and view records regardless of the role hierarchy or whoever owns the record.
I would set up a custom sharing rule so go to setup and search ‘Sharing Settings’. From there scroll down to your custom object, and create a sharing rule for the users you want to be able to edit each other’s records. This fill fix your error message regardless of role hierarchy, record ownership, etc.
