We have several users that cannot update the Assignee field. This has happened somewhat recently, and I do not know of any changes that have been made. The permission helper looks fine, but the user still receives "Assignee cannot be edited" when trying to assign issues. Below is one example of the permission helper screen:

I have also tried clearing cache, different browsers etc. and that did not help.
It seems that users that are explicitly defined in the People settings of the project, (company managed) have retained their rights, but not others.