'They appear to be fine' is not a 100% guarantee that they are. What does the access analyzer tell you? If this is the OOB 'My Groups Work' link in the navigator, it contains a script to get your groups. The role on the module itself only tells you if you should be able to see the module or not, not if you have access to the records behind it. Check if that script is accessible (getMyGroups()) for the users. 

Also, it can't be that it just suddenly stopped working. Something changed. Did you have any patches rolled out, store apps updated, or anything like that? The sys_update_xml table should tell you what changed between when it was working and now, and the 'upgrade history' can tell you if any apps were updated or not.