May or may not be the cause of the issue you're having, but some things to check when a user is unable to edit a feature class in an Enterprise GDB they should have permissions to edit:
If new install on new OS as you note, make sure the computer has the right version of the appropriate RDBMS access client installed (ex: SQL Server Native Client) for client to connect to RDBMS.
Also, check the settings of the version being edited. If the default version is set to protected, they could see it but not edit it, even if they have permissions to edit the feature class. More info on setting version permissions is at http://desktop.arcgis.com/en/arcmap/10.3/manage-data/geodatabases/creating-versions-and-setting-permissions.htm
And a final thing to check, though perhaps you have already, is to ensure they are actually connecting to the geodatabase as the user you gave edit permissions to. If you're using the integrated windows user based authentication, then this is likely not as much of an issue, but if you have a mixed or database only authentication model, then I would just double check that the *.sde file they used to access the feature class is actually using the correct user account. For example, if they are directly using or copied another user's pre-existing *.sde file to connect to the database, they could be unintentionally connecting with a user account that does not have access, even if the user account they should be using does have access. Again, this may or may not be likely in your given situation, but it doesn't hurt to check (especially if your users save *.sde files to a shared network drive other users can access...).
And of course, as is always recommended with any ESRI software bugs in my experience, make sure you try it directly adding the feature class to a brand new MXD after having restarted the computer, just to make sure there aren't any MXD or similar corruption issues.