What happens when they try? Are any error messages shown? Can the affected users attach files to the Documents tab on Contact records? Are any other users of the database able to attach files to the Documents tab in opportunities?
Are all the users trying to attach the same file? Does the error occur for any type of file? Can you test attaching the same file from the same location for both the affected and unaffected users? What happens? What happens if you change the password back to its previous value on one of the users you recently changed? Does this affect the ability to attach?