Also don't just check the Read and Write settings, check the Language Read and Language Write settings. If Language Write is set to deny, the user will not be able to edit any content in that language. To see those, you will have to click the Columns button and make sure that they are selected.

Check that the users' Roles have access to the Languages they are attempting to edit. You can do this by opening the Access Viewer, selecting the role, and navigating to System/Languages. Don't just check the Read and Write settings, it's the Language Read and Language Write settings that control access to Items based on that language. If Language Write is set to deny, the user will not be able to edit any content in that language. To see those, you will have to click the Columns button and make sure that they are selected.