Hi MT,
Although you say there have been no permission changes for these users, the cause of the problem may be due to permission changes for other classes of users as this can have an impact. You will need to hunt down people who have the ability to change user permissions, capabilities etc. and ask if they have made any changes. If this is unsuccessful, you may have to revert to a backup of your content store to restore the original state of the user privileges and capabilities,
Regards
Erik